Improved integrality gap upper bounds for traveling salesperson problems with distances one and two

We prove new integrality gap upper bounds for the traveling salesperson problem with distances one and two ((1,2)-TSP). We obtain these bounds by investigating the structure of the support graph of optimal solutions to the subtour elimination linear programming relaxation, with one additional cutting plane inequality.

For undirected (1,2)-TSP, our main results are as follows:

All instances have an integrality gap of at most 5/4.

Instances admitting half-integral solutions have integrality gap at most 7/6.

Instances admitting subcubic solutions Of cost at most the order of the instance have integrality gap at most 10/9, even without the cutting plane. This bound is tight, and holds in particular for basic solutions in the fractional 2-matching polytope with cost at most the order of the instance.

For directed (1,2)-TSP instances we show an integrality gap upper bound of 3/2 for general instances, and of 5/4 for instances admitting half-integral solutions.

We prove these bounds by providing local search algorithms that, in polynomial time, find 2-matchings with few components in the support of the solution. We show that the run times of our algorithms cannot be considerably improved under standard complexity-theoretic assumptions: we show that finding improved TSP solutions via local search is intractable for edge change parameterized by the size of the neighborhoods even for instances with distances one and two; this strengthens a result of Daniel Marx. (C) 2017 Elsevier B.V. All rights reserved.