3 papers
cs.DS2026
On (In)approximability of MaxMin Independent Set Reconfiguration
Hung P. Hoang, Naoto Ohsaka, Rin Saito +1
In the Independent Set Reconfiguration problem under the Token Addition/Removal rule, given a graph and two independent sets and of , we want to transform into $…
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…