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.