Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2013-14 > Improved Integrality Gap Upper Bounds for TSP with Distances One and Two
How to contact us

 

LSE 10 logo master_6


Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE

  

Enquiries: dom.events@lse.ac.uk 

  

Follow us online

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

Improved Integrality Gap Upper Bounds for TSP with Distances One and Two

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.

Share:Facebook|Twitter|LinkedIn|

 

Matthias-Mnich