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

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\mathrm{/}{2}^{\mathrm{\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.