2 papers
cs.DS2026
On the PLS-Completeness of -Opt Local Search for the Traveling Salesman Problem
Sophia Heimann, Hung P. Hoang, Stefan Hougardy
The -Opt algorithm is a local search algorithm for the traveling salesman problem. Starting with an initial tour, it iteratively replaces at most edges in the tour with the…
cs.DS2025
A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
Sophia Heimann, Hung P. Hoang, Stefan Hougardy
The -opt algorithm is one of the simplest and most widely used heuristics for solving the traveling salesman problem. Starting from an arbitrary tour, the -opt algorithm impr…