1 citations · 1 across the 4 of their papers we have counts for
8 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…
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…
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…
The Bottom-Left Algorithm for the Strip Packing Problem
Stefan Hougardy, Bart Zondervan
The bottom-left algorithm is a simple heuristic for the Strip Packing Problem. It places the rectangles in the given order at the lowest free position in the strip, using the left…
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…