# On the Integrality Ratio of the Subtour LP for Euclidean TSP

arXiv: https://arxiv.org/abs/1402.5904 · HTML: https://mlsanity.com/paper/1402.5904/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2014.

## Built on by (most cited first, 1 of 1)

- [Unsupervised Training for Neural TSP Solver](https://mlsanity.com/paper/2207.13667/) (2022)

## Abstract (arXiv)

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.