6

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?

Community
  • 1
Paul Miller
  • 161
  • 4
  • 5
    There is a subexponential $2^{O(\sqrt{n}\log n)}$-time algorithm for TSP in the plane (see page 90 of http://www.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. – Yonatan N Sep 04 '13 at 22:58
  • 4
    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. – David Eppstein Sep 05 '13 at 04:59

0 Answers0