An Improved Approximation Algorithm for TSP in the Half Integral Case

by Anna Karlin, Nathan Klein, and Shayan Oveis Gharan

Oded's comments

Being far from the area, I was not able to understand why this special case is considered the hardness, let alone that I am not convinced by integrality gap arguments. However, it is clear that this special case has attracted significant attention among the experts, and my basic principle is to respect the implicit (let alone explicit) opinions of the community of experts. In any case, this work presents an improvement, in a special case of scholarly interest, over the 1.5-approximation algorithm for general metric TSP (of Christofides, 1976).

The original abstract

We design a 1.49993-approximation algorithm for the metric traveling salesperson problem (TSP) for instances in which an optimal solution to the subtour linear programming relaxation is half-integral. These instances received significant attention over the last decade due to a conjecture of Schalekamp, Williamson and van Zuylen stating that half-integral LP solutions have the largest integrality gap over all fractional solutions. So, if the conjecture of Schalekamp et al. holds true, our result shows that the integrality gap of the subtour polytope is bounded away from 3/2.

See ArXiV 1908.00227.

Back to list of Oded's choices.