Are there any known exact algorithms for Euclidean TSP that take advantage of the inherent structure of the problem? Do any of these algorithms have better asymptotics than $O(2^n n^2)$ of a DP solution via Held-Karp? I am also interested in simplicity of implementation (I've seen a 10-line implementation of Held-Karp in Python).

Is this still the current state of the art?

  • 5
    $\begingroup$ There is a subexponential $2^{O(\sqrt{n}\log n)}$-time algorithm for TSP in the plane (see page 90 of nada.kth.se/~viggo/papers/phdthesis.pdf ). I'm not aware of any exact algorithms for higher dimensional Euclidean spaces, but I'm not terribly familiar with the literature on exact algorithms for TSP. $\endgroup$
    – Yonatan N
    Sep 4, 2013 at 22:58
  • 4
    $\begingroup$ It's not really an answer to your question, but the Held-Karp algorithm can be sped up to $O(2^n n^{3/2})$, as described by Timothy Chan in his invited talk at WADS this year. $\endgroup$ Sep 5, 2013 at 4:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.