Is the integrality gap of the subtour LP for metric TSP attained on half-integral vertices? (Schalekamp–Williamson–van Zuylen conjecture)

The subtour linear programming relaxation (Held–Karp relaxation) is the central polyhedral tool for the metric traveling salesperson problem, and its integrality gap — known to lie between $4/3$ and $3/2-\varepsilon$ and conjectured to equal $4/3$ — is among the most studied open quantities in combinatorial optimization. Schalekamp, Williamson, and van Zuylen conjectured that this worst case is attained on half-integral vertices of the subtour polytope, that is, on optimal solutions whose edge values all lie in $\{0, \frac{1}{2}, 1\}$; every known lower-bound example has this form. The conjecture, which is the surviving open core of Karlin–Klein–Oveis Gharan's 1.49993-approximation for half-integral instances (arXiv:1908.00227), remains open: the best upper bound on the half-integral gap is $1.49776$ (Klein–Taziki, 2025), no family of instances with non-half-integral LP optima exhibiting a worse ratio is known, and the literature through 2026 treats the conjecture as unresolved. An affirmative answer would transfer every upper bound on the half-integral gap to all metric instances, reducing the four-thirds conjecture to its half-integral case; a refutation would show that non-half-integral structure is essential and, whenever the half-integral gap equals $4/3$, would refute the four-thirds conjecture itself.

Background

In the metric traveling salesperson problem (metric TSP) we are given $n$ points and symmetric edge costs $c_e$ satisfying the triangle inequality, and seek a minimum-cost Hamiltonian cycle (a tour). The central polyhedral tool is the subtour LP, also called the Held–Karp relaxation:

$$\min \sum_e c_e x_e \quad \text{s.t.} \quad x(\delta(v)) = 2 \ \text{for all vertices } v, \qquad x(\delta(S)) \ge 2 \ \text{for all } \emptyset \neq S \subsetneq V, \qquad x_e \ge 0,$$

where $\delta(S)$ denotes the set of edges with exactly one endpoint in $S$ and $x(F) = \sum_{e \in F} x_e$. This LP relaxes the convex hull of incidence vectors of tours, so its optimum $\mathrm{LP}(I)$ lower-bounds the optimal tour cost $\mathrm{OPT}(I)$. The integrality gap of the subtour LP is the supremum of $\mathrm{OPT}(I)/\mathrm{LP}(I)$ over all metric instances; it is known to lie between $4/3$ and $3/2 - \varepsilon$ for some $\varepsilon > 10^{-36}$, and the four-thirds conjecture — one of the most famous open problems in approximation algorithms — asserts that it equals $4/3$. For roughly forty years the best upper bound was $3/2$, obtained by analyzing the classical algorithm of Christofides (compute a minimum spanning tree, add a minimum-cost perfect matching on its odd-degree vertices, and shortcut the resulting Eulerian walk) against the subtour LP.

A feasible solution of the subtour LP is half-integral if $x_e \in \{0, \frac{1}{2}, 1\}$ for every edge $e$. Half-integral solutions attract special attention for two reasons. First, all worst-case examples known for the subtour LP — instances where the ratio approaches $4/3$ — are half-integral. Second, Schalekamp, Williamson, and van Zuylen proved that the worst-case ratio between the cost of an optimal 2-matching (a spanning union of vertex-disjoint cycles, i.e., an integral solution of the LP without the cut constraints) and the subtour-LP optimum is attained on half-integral instances. They were thereby led to conjecture that the integrality gap itself is attained on half-integral vertices. Karlin, Klein, and Oveis Gharan (2019) proved a randomized 1.49993-approximation for instances whose optimal subtour-LP solution is half-integral; their algorithm samples a spanning tree from the maximum-entropy distribution with edge marginals $x$ (the highest-entropy probability distribution over spanning trees whose marginal edge probabilities equal the LP values, which tends to make the tree's odd-degree vertex set small) and adds a minimum-cost matching on the odd-degree vertices. Their bound is conditional on the Schalekamp–Williamson–van Zuylen conjecture: if the worst case is indeed half-integral, the general integrality gap is at most 1.49993. The best current bounds are $4/3 \le \mathrm{gap}_{HI} \le 1.49776$ for the half-integral gap and $\mathrm{gap} \le 3/2 - 10^{-36}$ in general, and the question of whether these two suprema coincide is the subject of this record.

Problem Statement

The Schalekamp–Williamson–van Zuylen conjecture. Let $\mathrm{gap}$ be the supremum of $\mathrm{OPT}(I)/\mathrm{LP}(I)$ over all metric TSP instances $I$ with $\mathrm{LP}(I) > 0$ (the ratio is defined only when the LP optimum is positive), where $\mathrm{OPT}(I)$ is the minimum tour cost and $\mathrm{LP}(I)$ is the subtour-LP optimum, and let $\mathrm{gap}_{HI}$ be the same supremum restricted to those instances $I$ in which some optimal subtour-LP solution is half-integral ($x_e \in \{0, \frac{1}{2}, 1\}$ for every edge $e$). Since instances admitting half-integral optima form a subclass, $\mathrm{gap} \ge \mathrm{gap}_{HI}$ always holds. Prove or disprove that

$$\mathrm{gap} = \mathrm{gap}_{HI},$$

equivalently, that for every metric TSP instance $I$,

$$\mathrm{OPT}(I)/\mathrm{LP}(I) \le \mathrm{gap}_{HI}.$$

An affirmative answer must hold for all metric instances, with no restriction on the structure of optimal LP solutions; combined with any upper bound $\alpha$ on the half-integral gap (currently $\alpha = 1.49776$) it would yield $\mathrm{gap} \le \alpha < 3/2$. A refutation must establish $\mathrm{gap} > \mathrm{gap}_{HI}$: given any proven upper bound $\alpha$ on $\mathrm{gap}_{HI}$ (currently $\alpha = 1.49776$), it suffices to exhibit a single metric instance $I$ with $\mathrm{OPT}(I)/\mathrm{LP}(I) > \alpha$, since then $\mathrm{gap} \ge \mathrm{OPT}(I)/\mathrm{LP}(I) > \alpha \ge \mathrm{gap}_{HI}$ (such an instance is necessarily not half-integral at an optimum, and a family of such instances likewise suffices). Without any such bound on $\mathrm{gap}_{HI}$, a single instance only lower-bounds $\mathrm{gap}$ and does not by itself settle the equality of suprema.

References

1. Anna Karlin, Nathan Klein, Shayan Oveis Gharan, 'An Improved Approximation Algorithm for TSP in the Half Integral Case', arXiv:1908.00227 (2019), doi:10.48550/arXiv.1908.00227, https://arxiv.org/abs/1908.00227
2. Frans Schalekamp, David P. Williamson, Anke van Zuylen, '2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture', Mathematics of Operations Research 39(2):403-417 (2014), doi:10.1287/moor.2013.0608, https://doi.org/10.1287/moor.2013.0608
3. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, 'A (Slightly) Improved Approximation Algorithm for Metric TSP', arXiv:2007.01409 (2020), doi:10.48550/arXiv.2007.01409, https://arxiv.org/abs/2007.01409
4. Anna Karlin, Nathan Klein, Shayan Oveis Gharan, 'A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP', arXiv:2105.10043 (2021), doi:10.48550/arXiv.2105.10043, https://arxiv.org/abs/2105.10043
5. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, 'A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP', arXiv:2212.06296 (2022), doi:10.48550/arXiv.2212.06296, https://arxiv.org/abs/2212.06296
6. Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar, 'Matroid-based TSP rounding for half-integral solutions', Mathematical Programming 206(1-2):541-576 (2024), doi:10.1007/s10107-024-02065-4, https://doi.org/10.1007/s10107-024-02065-4
7. Nathan Klein, Mehrshad Taziki, 'Dual Charging for Half-Integral TSP', arXiv:2507.17999 (2025), doi:10.48550/arXiv.2507.17999, https://arxiv.org/abs/2507.17999
8. Billy Jin, Nathan Klein, David P. Williamson, 'A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP', arXiv:2211.04639 (2022), doi:10.48550/arXiv.2211.04639, https://arxiv.org/abs/2211.04639
9. Billy Jin, Nathan Klein, David P. Williamson, 'A Lower Bound for the Max Entropy Algorithm for TSP', arXiv:2311.01950 (2023), doi:10.48550/arXiv.2311.01950, https://arxiv.org/abs/2311.01950
10. Billy Jin, Nathan Klein, David P. Williamson, 'Maximum Entropy is a 10/7-Approximation Algorithm for the TSP on Half-Integral Cycle Cut Instances', arXiv:2607.01536 (2026), doi:10.48550/arXiv.2607.01536, https://arxiv.org/abs/2607.01536
11. Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, Lu Wang, 'A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case', SIAM Journal on Discrete Mathematics 36(3):1730-1747 (2022), doi:10.1137/20M1372822, https://doi.org/10.1137/20M1372822
12. Arash Haddadan, Alantha Newman, 'Towards Improving Christofides Algorithm for Half-Integer TSP', ESA 2019, LIPIcs 144:56:1-56:12, doi:10.4230/LIPIcs.ESA.2019.56, https://doi.org/10.4230/LIPIcs.ESA.2019.56
13. Tullio Villa, Eleonora Vercesi, Janos Barta, Monaldo Mastrolilli, 'The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-zero Components', arXiv:2507.07003 (2025), doi:10.48550/arXiv.2507.07003, https://arxiv.org/abs/2507.07003
14. William Cook, Stefan Hougardy, Moritz Petrich, 'Extending Exact Integrality Gap Computations for the Metric TSP', arXiv:2603.12995 (2026), doi:10.48550/arXiv.2603.12995, https://arxiv.org/abs/2603.12995
15. Toshiaki Yamanaka, 'TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima', arXiv:2511.11215 (2025), doi:10.48550/arXiv.2511.11215, https://arxiv.org/abs/2511.11215
16. Michael Held, Richard M. Karp, 'The Traveling-Salesman Problem and Minimum Spanning Trees', Operations Research 18(6):1138-1162 (1970), doi:10.1287/opre.18.6.1138, https://doi.org/10.1287/opre.18.6.1138