4 papers
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…
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 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
Stefan Hougardy, Bart Zondervan
In the Strip Packing problem, we are given a vertical strip of fixed width and unbounded height, along with a set of axis-parallel rectangles. The task is to place all rectangles w…
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…