6
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 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 '13 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$ – David Eppstein Sep 5 '13 at 4:59

Your Answer

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

Browse other questions tagged or ask your own question.