Wednesday 19th March 2014, 4.30pm - 5.30pm
32L.G.03, LSE
Matthias Mnich
TU Darmstadt
Personal profile
Abstract:
We study the structure of solutions to linear programming formulations for the traveling salesperson problem (TSP). We perform a detailed analysis of the support of the subtour elimination linear programming relaxation, which leads to algorithms that find 2-matchings with few components in polynomial time. The number of components directly leads to integrality gap upper bounds for the TSP with distances one and two, for both undirected and directed graphs.
Our main results for fractionally Hamiltonian instances are:
-
For undirected instances we obtain an integrality gap upper bound of 5/4 without any restrictions, of 7/6 if the optimal LP solution is half-integral, and of 10/9 if there is an optimal solution that is a basic solution of the fractional 2-matching polytope.
-
For directed instances we obtain an integrality gap upper bound of 3/2, and of 4/3 if given an optimal 1/2-integral solution. Our algorithms perform sequences of local improvements that harness the structure of the support.
Additionally, we show that relying on the structure of the support is not an artifact of our algorithm, but is necessary under standard complexity-theoretic assumptions: we show that finding improved solutions via local search is W[1]-hard for k-edge change neighborhoods even for the TSP with distances one and two, which strengthens a result of Dániel Marx.
This is joint work with Tobias Moemke.