A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP

We show that for some $ϵ>{10}^{-36}$ and any metric TSP instance, the max entropy algorithm returns a solution of expected cost at most $\frac{3}{2}-ϵ$ times the cost of the optimal solution to the subtour elimination LP. This implies that the integrality gap of the subtour LP is at most $\frac{3}{2}-ϵ$. This analysis also shows that there is a randomized $\frac{3}{2}-ϵ$ approximation for the 2-edge-connected multi-subgraph problem, improving upon Christofides’ algorithm.