TSP Escapes the $O(2^n n^2)$ Curse
<|reference_start|>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 / 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\"ive algorithms exist.<|reference_end|>
@article{stoian2024tsp,
    title={TSP Escapes the $O(2^n n^2)$ Curse},
    author={Mihail Stoian},
    journal={arXiv preprint arXiv:2405.03018},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.03018},
    primaryClass={cs.DS cs.CC}
}