The traveling salesman problem (TSP) is one of the most well studied problems in combinatorial optimization. The TSP is known to be NP-hard, even in the case that distances are symmetric and obey the triangle inequality. Because of the NP-hardness of the traveling salesman problem, researchers have considered approximation algorithms for the problem. The best approximation algorithm currently known is a 3/2-approximation algorithm given by Christofides in 1976.

There is a well-known, natural direction for making progress which has also defied improvement for nearly thirty years: the use of linear programming. The subtour LP is a linear programming relaxation of the TSP introduced by Dantzig, Fulkerson, and Johnson in 1954. The subtour LP is known to give excellent lower bounds on TSP instances in practice, coming within a percent or two of the length of the optimal tour. However, its theoretical worst-case is not well understood. It has been conjectured for some time that the worst-case ratio, taken over all instances of the problem, of the value of the optimal tour to the value of the subtour LP (the “integrality gap” of the subtour LP) is at most 4/3.

In this talk, and a talk at CWI on October 4th, we will present some new results that refine our understanding of the subtour LP. This talk focuses on the special case in which all distances are either 1 or 2.

We show that the integrality gap for this special case is at most $106/81 approx 1.31 < 4/3$; this is the first bound on the integrality gap of the subtour LP strictly less than 4/3 known for an interesting special case of the TSP. If we make additional assumptions on the structure of the subtour solution, we can show even stronger results. For one particular case we can show that the gap is at most 10/9, which is tight.

Althought the two talks cover two aspects of the same problem, they can be attended independently.

This is joint work with Jiawei Qian, David Williamson and Anke van Zuylen