5
$\begingroup$

Symmetric/Metric TSP can be solved via the Held-Karp algorithm in $\mathcal O(n^2 2^n)$.

See A dynamic programming approach to sequencing problems by Michael Held and Richard M. Karp, 1962.

In Exact Algorithms for NP-Hard Problems: A Survey (PDF) Woeginger writes:

This result was published in 1962, and from nowadays point of view almost looks trivial. Still, it yields the best time complexity that is known today.

Thus, this is the best known upper-bound.

Question:

Are there any better results for Euclidean TSP? Or does that best-known bound apply to Euclidean TSP as well.

How is Euclidean TSP different? Well,

  • Euclidean TSP can be encoded into $\mathcal O(n \log m)$ space, where $n$ is the number of cities, and $m$ is the bound on the integer coordinates of the city locations. As opposed to (sym)metric TSP variants, which essentially require a distance matrix of size $\mathcal O(n^2 \log m)$. Thus, it might be easier to solve; for example, perhaps Euclidean TSP can be more easily encoded into k-SAT, because the distance function is implicit.
  • Contrary to popular notion, Euclidean TSP's reduction from k-SAT is quite different from (sym)metric TSP. UHC (undirected Hamiltonian cycle), symmetric TSP, and metric TSP are pretty directly related to each-other. But formulations of reductions from (sym)metric TSP to Euclidean TSP are not easy to come by. Paragraph, from interesting article, The Travelling Salesman’s Power by K. W. Regan (bold mine):

    Now the reductions from 3SAT to TSP, especially Euclidean TSP, are less familiar, and we ascribe this to their being far more “expansive.” Texts usually reduce 3SAT to Hamiltonian Cycle, then present the latter as a special case of TSP, but this does not apply to Euclidean TSP. The ${\mathsf{NP}}$-completeness of Euclidean TSP took a few years until being shown by Christos Papadimitriou, and a 1981 paper by him with Alon Itai and Jayme Luiz Szwarcfiter advertised a “new, relatively simple, proof.” This proof uses vertex-induced subgraphs of the grid graph in the plane, for which the shortest possible TSP tour and any Hamiltonian cycle have the same length. Despite this simplification, the gadgets involved are large—a diagram of one occupies most of one journal page.

    Hunting down k-SAT $\rightarrow$ Euclidean TSP reductions is quite an adventure; so far I've found two of them. One $\rm k\text{-}SAT \rightarrow CircuitSAT \rightarrow PlanarCircuitSAT \rightarrow EuclideanTSP$, and another, even tougher one to find, $\rm k\text{-}SAT \rightarrow DHC \rightarrow UHC \rightarrow PlanarUHC \rightarrow EuclideanTSP$. The latter reduction can perhaps be seen to make Euclidean TSP parallel (sym)metric TSP.

$\endgroup$
4
$\begingroup$

One can exploit planar separator structures in a geometric setting and thus solve Euclidean TSP exactly in $O(n^{c \sqrt{n}})$ time, where $c$ is some small constant greater than 1. There's at least three simultaneous results for this; Smith's PhD thesis [1], Kann's PhD thesis [2], and Hwang et al. [3]. Each algorithm has a running time of $O^*(c^{\sqrt{n} \log n})$. This is much better than $O(n^2 2^n)$. As far as I know, it is still an open question whether the running time can be improved by say getting rid of the logarithmic term.


[1] W.D. Smith, Studies in computational geometry motivated by mesh generation. Ph.D. Thesis, Princeton University, Princeton.

[2] V. Kann, On the approximability of NP-complete optimization problems, Ph.D. Thesis, Kungliga Tekniska Högskolan, Stockholm, 1992.

[3] R.Z. Hwang, R.C. Chang, R.C.T. Lee, The searching over separators strategy to solve some NP-hard problems in subexponential time, Algorithmica 9 (1993) 398–423.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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