The four-thirds integrality gap for metric routing
Let $n \ge 3$ and let $c$ be a metric on the vertices of the complete graph $K_n$: edge costs $c_e \ge 0$ satisfying the triangle inequality. Let $\mathrm{OPT}(c)$ be the cost of a cheapest Hamiltonian cycle, and let $\mathrm{HK}(c)$, the Held–Karp bound, be the optimal value of the subtour relaxation $$\min \Bigl\{ \sum_e c_e x_e \;:\; x \ge 0,\ \sum_{e \ni v} x_e = 2 \text{ for every vertex } v,\ \sum_{e \in \delta(S)} x_e \ge 2 \text{ for every } \varnothing \ne S \subsetneq V(K_n) \Bigr\},$$ where $\delta(S)$ is the set of edges with exactly one end in $S$. Wolsey proved $\mathrm{OPT}(c) \le \tfrac32 \mathrm{HK}(c)$, and Karlin, Klein and Oveis Gharan improved the factor to $\tfrac32 - \varepsilon$ for a constant $\varepsilon > 10^{-36}$. There are metrics for which $\mathrm{OPT}(c)/\mathrm{HK}(c)$ is arbitrarily close to $\tfrac43$. The inequality below was verified by computer for $n \le 10$ by Benoit and Boyd and for $n \le 16$ by Cook, Hougardy and Petrich, and Jin, Klein and Williamson proved it for half-integral cycle cut instances.
Problem. Is $\mathrm{OPT}(c) \le \tfrac43 \mathrm{HK}(c)$ for every $n \ge 3$ and every such metric $c$?
Source: The 4/3 conjecture for the subtour relaxation of the metric traveling salesman problem: Williamson (1990) and Goemans (1995); see Cook, Hougardy and Petrich (2026).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- OC
- Keywords
- AIM Open Applied Problems, integrality gaps, linear programming relaxations, traveling salesman problem
References
@mastersthesis{williamson1990,
author = {Williamson, David P.},
title = {Analysis of the {H}eld--{K}arp heuristic for the traveling salesman problem},
school = {Massachusetts Institute of Technology},
year = {1990},
}
@article{goemans1995,
author = {Goemans, Michel X.},
title = {Worst-case comparison of valid inequalities for the {TSP}},
journal = {Math. Programming},
volume = {69},
number = {1-3},
year = {1995},
pages = {335--349},
doi = {10.1007/BF01585563},
}
@misc{cook2026,
author = {Cook, William and Hougardy, Stefan and Petrich, Moritz},
title = {Extending exact integrality gap computations for the metric {TSP}},
year = {2026},
eprint = {2603.12995},
archivePrefix = {arXiv},
note = {v5, 8 September 2026},
}
@article{wolsey1980,
author = {Wolsey, Laurence A.},
title = {Heuristic analysis, linear programming and branch and bound},
journal = {Math. Programming Stud.},
volume = {13},
year = {1980},
pages = {121--134},
doi = {10.1007/BFb0120913},
}
@inproceedings{karlin2022,
author = {Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan},
title = {A (slightly) improved bound on the integrality gap of the subtour {LP} for {TSP}},
booktitle = {2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)},
publisher = {IEEE},
year = {2022},
pages = {832--843},
doi = {10.1109/FOCS54457.2022.00084},
eprint = {2105.10043},
archivePrefix = {arXiv},
}
@article{benoit2008,
author = {Benoit, Genevi{\`e}ve and Boyd, Sylvia},
title = {Finding the exact integrality gap for small traveling salesman problems},
journal = {Math. Oper. Res.},
volume = {33},
number = {4},
year = {2008},
pages = {921--931},
doi = {10.1287/moor.1080.0337},
}
@article{jin2025,
author = {Jin, Billy and Klein, Nathan and Williamson, David P.},
title = {A $\frac{4}{3}$-approximation algorithm for half-integral cycle cut instances of the {TSP}},
journal = {Math. Program.},
volume = {210},
number = {1-2},
year = {2025},
pages = {511--538},
doi = {10.1007/s10107-025-02193-5},
eprint = {2211.04639},
archivePrefix = {arXiv},
}
@misc{jin2026,
author = {Jin, Billy and Klein, Nathan and Williamson, David P.},
title = {Maximum entropy is a 10/7-approximation algorithm for the {TSP} on half-integral cycle cut instances},
year = {2026},
eprint = {2607.01536},
archivePrefix = {arXiv},
}
@misc{aim-metric-tsp-four-thirds,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The four-thirds integrality gap for metric routing}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/275-metric-tsp-four-thirds.md},
note = {Entry 275 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00453, "The four-thirds integrality gap for metric routing", clopen.solutions.