5 papers
Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
Sophia Heimann, Hung P. Hoang, Stefan Hougardy
We prove the all-exp property for the Traveling Salesman Problem with the -opt neighborhood, and for - and -Maximum Constraint Assignment with the flip neighbo…
Exponential Local Search in Bounded-Occurrence MAX-CSP
Sophia Heimann, Hung P. Hoang, Stefan Hougardy
We study the number of improving steps that local search may require for -MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constrai…
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…
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…
The -Opt algorithm for the Traveling Salesman Problem has exponential running time for
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…