mlsanityData to 14 Oct 2026

On the Integrality Ratio of the Subtour LP for Euclidean TSP

arXiv 1402.5904 ↗First posted 24 Feb 2014cs.DM cs.DS math.COcited by 1

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2022: 1.

1 paper.

  1. 2022Unsupervised Training for Neural TSP Solvercited by 9