An Improved Approximation Algorithm for TSP in the Half Integral Case

Anna Karlin, Nathan Klein, Shayan Oveis Gharan

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 relaxa…