## 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.