On the Integrality Ratio of the Subtour LP for Euclidean TSP

Abstract

A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is $4/3$. A well known family of graphic TSP instances achieves this lower bound asymptotically. For Euclidean TSP the best known lower bound on the integrality ratio was $8/7$. We improve this value by presenting a family of Euclidean TSP instances for which the integrality ratio of the subtour LP converges to 4/3.

References in corpus (1)

• On the Integrality Gap of the Subtour LP for the 1,2-TSP