1 citations · 1 across the 4 of their papers we have counts for
4 papers · 1 filter
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…
Extending Exact Integrality Gap Computations for the Metric TSP
William Cook, Stefan Hougardy, Moritz Petrich
The subtour relaxation of the traveling salesman problem (TSP) plays a central role in approximation algorithms and polyhedral studies of the TSP. A long-standing conjecture assert…