From: israel@math.ubc.ca (Robert Israel) Subject: Re: TSP approx algorithm Date: 10 May 2000 00:01:19 GMT Newsgroups: sci.math.research Summary: [missing] In article <8f81b8$pfm$1@news.acns.nwu.edu>, MJ Lee wrote: >if my approx algo is to "keep on picking the closest point", >how can i proof this algo has a ratio bound of 2? You really should be more precise about what you mean by this. However, it sounds like you could be talking about the following: for the symmetric traveling salesman problem on a complete graph G (satisfying the triangle inequality), you can obtain a Hamiltonian tour with less than twice the distance of an optimal tour as follows: 1) find a minimal spanning tree for G. This can be done using a greedy algorithm: start with one vertex, and at each step add the shortest edge that connects a new vertex to the tree. 2) form the tour by traversing the minimal spanning tree, skipping vertices already visited. Thus if your spanning tree was A | B - C - D - E | | F G you might start at A, traverse it as ACDEDGDCFCBCA, and form the tour ACDEGFBA. For a proof of the bound, note that if you remove one edge from a Hamiltonian tour, you obtain a spanning tree. Therefore the length of the minimal spanning tree is less than the length of an optimal tour. Now in traversing the tree you cover each of its edges twice, and the triangle inequality ensures that by skipping already-visited vertices you don't increase the length. This is not the same as the "nearest neighbour method" which starts with a given vertex and always goes to the closest unvisited vertex (and then back to the start at the end). I don't think that has a bound of 2. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: Mark Evans Jeffcoat Subject: Re: TSP approx algorithm Date: 10 May 2000 20:35:20 GMT Newsgroups: sci.math.research Robert Israel wrote: :>This is not the same as the "nearest neighbour method" which starts :>with a given vertex and always goes to the closest unvisited vertex :>(and then back to the start at the end). I don't think that has a :>bound of 2. A nearest neighbor bound is given by Rosenkrantz, Stearns, and Lewis (1977, SIAM Journal on Computing); with n nodes, the NN tour is not more than 1/2*[(log2 n)]+1/2 (Where [x] is the smallest integer greater than x.), if your distance satisfies the triangle inequality. They also describe TSPs where NN produces tours almost this bad. -- Mark Jeffcoat