<p>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).</p>

<p>Is <a href="https://cstheory.stackexchange.com/a/11557/17264">this</a> still the current state of the art?</p>

CC BY-SA 3.0
2013-09-04T22:58:54.007Z
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
CC BY-SA 3.0
2013-09-05T04:59:40.260Z
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
<tsp><dynamic-programming>
Euclidean TSP algorithms
Paul Miller
# Euclidean TSP algorithms

(Asked by: username_0 on 2013-09-04)

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](https://cstheory.stackexchange.com/a/11557/17264) still the current state of the art?

**Tags:** tsp, dynamic-programming
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 0 answers

