The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
<|reference_start|>The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$: The $k$-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most $k$ edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the $k$-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the $k$-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires $k \gg 1000$ and has a substantial gap. We show the two properties above for a much smaller value of $k$, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for $k \geq 17$ and the exponential running time for $k \geq 5$.<|reference_end|>
@article{heimann2024the,
    title={The $k$-Opt algorithm for the Traveling Salesman Problem has exponential
  running time for $k \ge 5$},
    author={Sophia Heimann, Hung P. Hoang, Stefan Hougardy},
    journal={arXiv preprint arXiv:2402.07061},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07061},
    primaryClass={cs.DS cs.DM math.CO}
}