# Euclidean TSP algorithms

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?

• 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. – Yonatan N Sep 4 '13 at 22:58
• 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 5 '13 at 4:59