From: KIMON.ATH.FORTHNET.GR@popper.forthnet.gr (Kimon Spiliopoulos) Newsgroups: sci.math Subject: Re: Approximate Algorithms for the Traveling Salesman Problem Date: Sun, 23 Mar 1997 21:08:42 GMT harden wrote: >I have read somewhere that there is a polynomial time approximation >algorithm for the traveling salesman problem that produces a tour whose >cost is at most 2 times that of the optimal tour. Am I confused, or does >there exist such an algorithm, and, if so, how does it work? >Any help would be appreciated. The best known guarantee (provided that the distances obey the triangle inequality) is 1.5 times the cost of the optimal tour, with Christofides algorithm, running in less than O(n^3) time. The construction is easy: a. Find a minimum spanning tree on the vertices. b. Add the edges of a minimum cost matching on the odd degree vertices of the tree - this is the less than O(n^3) step (I don't know the current best computational result). c. Use shortcuts to have each vertex visited exactly once. The tour can be improved by various methods (eg edge swaps to make it 2 or 3-optimal etc) but not the 1.5 guarantee. Best regards Kimon ============================================================================== From: resta@imc.pi.cnr.it (Giovanni Resta) Newsgroups: sci.math Subject: Re: Approximate Algorithms for the Traveling Salesman Problem Date: Mon, 24 Mar 1997 17:14:18 +0100 > harden wrote: > > >I have read somewhere that there is a polynomial time approximation > >algorithm for the traveling salesman problem that produces a tour whose > >cost is at most 2 times that of the optimal tour. Am I confused, or does > >there exist such an algorithm, and, if so, how does it work? > > >Any help would be appreciated. approximate methods can easily obtain solutions that are 2% far from optimal (say 1.02 times the optimal) in particular in the case of Euclidian TSP, in which distances satisfies triangular inequalities. This can be obtained using iterated local search. Unfortunately, even if these euristics perform very well in practice (David Johnson approximated the solution of instances with more than 1,000,000 cities), you have no theoretical guarantee about the goodness of approximation. Giovanni.