The factor-two integrality gap for asymmetric metric routing
Let $V = \{1, \dots, n\}$ with $n \ge 3$, and assign a finite cost $c_{ij} \ge 0$ to each ordered pair of distinct vertices, with $c_{ii} = 0$ and the directed triangle inequality $c_{ik} \le c_{ij} + c_{jk}$ for all $i, j, k \in V$; the costs $c_{ij}$ and $c_{ji}$ may differ. Let $\operatorname{OPT}(c)$ be the minimum cost of a directed Hamiltonian cycle, and let $\operatorname{HK}(c)$ be the value of the subtour linear program $$ \begin{aligned} \operatorname{HK}(c) = \min\quad & \sum_{i \ne j} c_{ij} x_{ij} \\ \text{subject to}\quad & \sum_{j \ne i} x_{ij} = \sum_{j \ne i} x_{ji} = 1 && (i \in V), \\ & \sum_{i \in S,\, j \notin S} x_{ij} \ge 1 && (\varnothing \ne S \subsetneq V), \\ & x_{ij} \ge 0 && (i \ne j). \end{aligned} $$
The supremum of $\operatorname{OPT}(c)/\operatorname{HK}(c)$ over all instances is the integrality ratio of this relaxation of the asymmetric traveling salesman problem; Traub and Vygen show that it equals the integrality ratio of the corresponding relaxation for arbitrary nonnegative costs on a strongly connected digraph. Charikar, Goemans and Karloff proved that it is at least $2$. Svensson, Tarnawski and Végh proved that it is bounded by a constant, and Traub and Vygen brought the bound down to $22$ and then to $17$. Vygen, in a 2026 preprint, proves $\operatorname{OPT}(c) \le (12 + 2\sqrt{2} + \varepsilon)\operatorname{HK}(c)$ for every $\varepsilon > 0$.
Problem. Does every such instance satisfy $\operatorname{OPT}(c) \le 2\, \operatorname{HK}(c)$?
Source: Traub and Vygen (2024), Open Problem 3.19 (prove or disprove that the integrality ratio is 2), after the lower bound of Charikar, Goemans and Karloff (2006). Stated as an upper bound by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, integrality gaps, linear programming relaxations, traveling salesman problem
References
@book{traub2024,
author = {Traub, Vera and Vygen, Jens},
title = {Approximation Algorithms for Traveling Salesman Problems},
publisher = {Cambridge University Press},
address = {Cambridge},
year = {2024},
doi = {10.1017/9781009445436},
}
@article{charikar2006,
author = {Charikar, Moses and Goemans, Michel X. and Karloff, Howard},
title = {On the integrality ratio for the asymmetric traveling salesman problem},
journal = {Math. Oper. Res.},
volume = {31},
number = {2},
year = {2006},
pages = {245--252},
doi = {10.1287/moor.1060.0191},
}
@article{svensson2020,
author = {Svensson, Ola and Tarnawski, Jakub and V{\'e}gh, L{\'a}szl{\'o} A.},
title = {A constant-factor approximation algorithm for the asymmetric traveling salesman problem},
journal = {J. ACM},
volume = {67},
number = {6},
year = {2020},
pages = {Art. 37, 1--53},
doi = {10.1145/3424306},
}
@article{traub2022,
author = {Traub, Vera and Vygen, Jens},
title = {An improved approximation algorithm for the asymmetric traveling salesman problem},
journal = {SIAM J. Comput.},
volume = {51},
number = {1},
year = {2022},
pages = {139--173},
doi = {10.1137/20M1339313},
}
@misc{vygen2026,
author = {Vygen, Jens},
title = {Better approximation guarantee for {A}symmetric {TSP}},
year = {2026},
eprint = {2603.14334},
archivePrefix = {arXiv},
}
@misc{aim-asymmetric-tsp-integrality-gap,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The factor-two integrality gap for asymmetric metric routing}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/312-asymmetric-tsp-integrality-gap.md},
note = {Entry 312 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-00406, "The factor-two integrality gap for asymmetric metric routing", clopen.solutions.