2
$\begingroup$

I am trying to find a way to solve Euclidean TSP in a polynomial time. I looked at some papers but I couldn't decide which one is better. What is the general approximation algorithm for solving this problem in polynomial time?

$\endgroup$
5
  • 1
    $\begingroup$ This reference looks pretty recent: informatik.uni-kiel.de/~gej/publ/tsp_backbone_shab.pdf. $\endgroup$ Mar 10, 2014 at 0:48
  • 1
    $\begingroup$ technically its NP complete right? $\endgroup$
    – vzn
    Mar 10, 2014 at 3:54
  • 1
    $\begingroup$ @vzn yes, it is. That is why we are trying to find a approximate solution. $\endgroup$ Mar 10, 2014 at 4:54
  • 2
    $\begingroup$ You'd have to try several approximations, they could give better or worse results with your particular type of problem. $\endgroup$
    – vonbrand
    Mar 10, 2014 at 18:29
  • $\begingroup$ There are plenty; which have you investigated and what are your results? Asking for a survey of decades of research is not a good SE question. Also, note that "the best algorithm" does not exist (ever); you need to specify your requirements (solution quality, runtime, memory, parallelisable, ...) $\endgroup$
    – Raphael
    Apr 13, 2014 at 9:52

1 Answer 1

2
$\begingroup$

Euclidean TSP is not even known to be in $NP$, basically because it seems that even to verify if there is a hamiltonian cycle of length at most $k$, we need to computing the sum of square roots. But the problem "$\sum_{i}\sqrt{a_i}<k?$" is not known to be in $NP$.

Anyway Euclidean TSP has $PTAS$.

$\endgroup$
2
  • $\begingroup$ @FrankW It's only known to be in NP if the distances are discretized -- Papadimitriou's NP-completeness proof takes distance to be the floor of the Euclidean distance. Otherwise, as eig says, the square root sum problem isn't known to be in NP and Euclidean TSP involves comparing sums of square roots. You'll notice that Arora's PTAS paper only ever describes Euclidean TSP as "NP-hard"; never "NP-complete". $\endgroup$ Mar 13, 2014 at 22:29
  • 3
    $\begingroup$ OK, it actually didn't occur to me to think of real valued distances in the context of NP. Now I see that you do not have to give the distances as input but can infer them from the (rational) coordinates of the points and thus avoid the "you can't input reals into a TM" problem. $\endgroup$
    – FrankW
    Mar 13, 2014 at 23:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.