TSP Escapes the $O(2^n{n}^2)$ Curse

Abstract

The dynamic programming solution to the traveling salesman problem due to Bellman, and independently Held and Karp, runs in time $O(2^n{n}^2)$, with no improvement in the last sixty years. We break this barrier for the first time by designing an algorithm that runs in deterministic time $2^n{n}^2/2^{\Omega (\sqrt{\log n})}$. We achieve this by strategically remodeling the dynamic programming recursion as a min-plus matrix product, for which faster-than-naïve algorithms exist.

arXiv commentminor text improvements; added reference to time-space tradeoff paper; original results unchanged