Metric TSP subtour-LP integrality-gap constant

Description of constant

In the symmetric metric traveling salesman problem, one is given a complete graph $K_n=(V,E)$ with a nonnegative symmetric cost function $c:E\to {\mathbb{R}}_{\ge 0}$ satisfying the triangle inequality. For $S\subseteq V$, let $\delta (S)$ denote the set of edges with exactly one endpoint in $S$, and write $$\begin{gathered} \delta (v):=\delta ( \\ v \\ ) \end{gathered}$$. Let $\mathrm{TSP}(c)$ be the minimum cost of a Hamiltonian cycle in $K_n$. The subtour-elimination linear program has optimum value $$\mathrm{SEP}(c):=\min \sum _{e\in E}{c}_e{x}_e$$ subject to $$\sum _{e\in \delta (v)}{x}_e=2\text{for all }v\in V,$$ $$\sum _{e\in \delta (S)}{x}_e\ge 2\text{for all }\varnothing ⊊S⊊V,$$ $$x_e\ge 0\text{for all }e\in E.$$ <a href="#KKO2022-metric-def">[KKO2022-metric-def]</a> <a href="#KKO2022-lp-def">[KKO2022-lp-def]</a>

We define $$C_{75}:=\sup \frac{\mathrm{TSP}(c)}{\mathrm{SEP}(c)},$$ where the supremum ranges over all finite metric TSP instances. Equivalently, $C_{75}$ is the worst-case integrality gap of the subtour-elimination LP for metric TSP. <a href="#Hou2014-gap-4over3">[Hou2014-gap-4over3]</a>

The best established range is $$\frac{4}{3}\le C_{75}\le \frac{3}{2}-2.18\cdot 10^{-34},$$ and the long-standing conjecture is that $C_{75}=\frac{4}{3}$. <a href="#Hou2014-gap-4over3">[Hou2014-gap-4over3]</a> <a href="#GKL2024-ub-2p18e-34">[GKL2024-ub-2p18e-34]</a> <a href="#KKO2022-ub-eps">[KKO2022-ub-eps]</a>

---

Known upper bounds

---

Known lower bounds

Additional comments and links

• The $4/3$ conjecture. The central conjecture is that $C_{75}=4/3$. <a href="#KKO2022-ub-eps">[KKO2022-ub-eps]</a>

• Recent partial progress. Villa, Vercesi, Barta, and Mastrolilli proved the conjectured bound for instances whose optimal SEP solution has at most $n+6$ non-zero components. <a href="#VVBM2025-nplus6">[VVBM2025-nplus6]</a>

• Algorithmic significance. The better-than-$3/2$ breakthroughs for general metric TSP work by rounding solutions of this LP, so $C_{75}$ is the exact worst-case constant attached to this relaxation. <a href="#KKO2022-lp-def">[KKO2022-lp-def]</a> <a href="#GKL2024-ub-2p18e-34">[GKL2024-ub-2p18e-34]</a>

References

• <a id="GKL2024"></a>[GKL2024] Gurvits, Leonid; Klein, Nathan; Leake, Jonathan. From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. In: 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Leibniz International Proceedings in Informatics (LIPIcs) 297 (2024), 79:1–79:20. DOI: 10.4230/LIPIcs.ICALP.2024.79. arXiv PDF: 2311.09072. Google Scholar
• <a id="GKL2024-ub-2p18e-34"></a>[GKL2024-ub-2p18e-34] loc: arXiv PDF p. 10 (paper p. 9), Section 4.2 “Summary of Probabilistic Bounds and New Approximation Factor”, file arXiv:2311.09072 PDF quote: “Lemma 4.5. Let $p$ be a lower bound on the probabilities guaranteed by (1) - (6) for ${ϵ}_{1/2}\le 0.0002$, and suppose $p\le 10^{-4}$. Then given $x\in PSub$, the max entropy algorithm returns a solution of expected cost at most $(3/2-9.7p^2\cdot 10^{-17})\cdot c(x)$. As we improve the bounds on $p$ to $1.5\cdot 10^{-9}$, an immediate corollary is the following: Corollary 4.6. The max entropy algorithm is a $3/2-2.18\cdot 10^{-34}$ approximation algorithm for metric TSP.”

• <a id="Hou2014"></a>[Hou2014] Hougardy, Stefan. On the integrality ratio of the subtour LP for Euclidean TSP. Operations Research Letters 42 (2014), no. 8, 495–499. DOI: 10.1016/j.orl.2014.08.009. arXiv PDF: 1402.5904v3. Google Scholar
• <a id="Hou2014-gap-4over3"></a>[Hou2014-gap-4over3] loc: arXiv v3 PDF p. 2, Section 1 “Introduction”, file arXiv:1402.5904v3 PDF quote: “The integrality ratio of the subtour LP for the metric TSP is the supremum of the length of an optimum TSP tour over the optimum solution of the subtour LP. Wolsey [11] has shown that the integrality ratio of the subtour LP for metric TSP is at most $3/2$. A well known conjecture states that the integrality ratio of the subtour LP for metric TSP is $4/3$. This conjecture seems to be mentioned for the first time in 1990 [10, page 35] but according to [4] it was already well known several years before. A proof of this conjecture yields a polynomial time algorithm that approximates the value of an optimum TSP tour within a factor of $4/3$. It is known that the integrality ratio of the subtour LP is at least $4/3$ as there exists a family of metric TSP instances whose integrality ratio converges to $4/3$ (see for example [10]).”

• <a id="KKO2022"></a>[KKO2022] Karlin, Anna R.; Klein, Nathan; Oveis Gharan, Shayan. A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), 832–843. DOI: 10.1109/FOCS54457.2022.00084. arXiv PDF: 2105.10043v3. Google Scholar
• <a id="KKO2022-metric-def"></a>[KKO2022-metric-def] loc: arXiv v3 PDF p. 3 (paper p. 1), Section 1 “Introduction”, file arXiv:2105.10043v3 PDF quote: “In an instance of TSP we are given a set of $n$ cities $V$ along with their pairwise symmetric distances, $c:V\times V\to {\mathbb{R}}_{\ge 0}$. The goal is to find a Hamiltonian cycle of minimum cost. In the metric TSP problem, which we study here, the distances satisfy the triangle inequality. Therefore, the problem is equivalent to finding a closed Eulerian connected walk of minimum cost.”
• <a id="KKO2022-lp-def"></a>[KKO2022-lp-def] loc: arXiv v3 PDF p. 3 (paper p. 1), Section 1 “Introduction”, file arXiv:2105.10043v3 PDF quote: “The method introduced in [KKO21] exploits the optimum solution to the following linear programming relaxation of metric TSP studied by [DFJ59; HK70; GB93], also known as the subtour elimination LP..."
• <a id="KKO2022-ub-eps"></a>[KKO2022-ub-eps] loc: arXiv v3 PDF p. 3 (paper p. 1), Section 1 “Introduction”, file arXiv:2105.10043v3 PDF quote: “However, [KKO21] did not show that the integrality gap of the subtour elimination polytope is bounded below $3/2$, and therefore did not make progress towards the ‘$4/3$ conjecture’ which posits that the integrality gap of LP (1) is $4/3$. In this work we remedy this discrepancy by proving the following theorem, improving upon the bound of $3/2$ from Wolsey [Wol80] in 1980: Theorem 1.1. Let $x$ be a solution to LP (1) for a TSP instance. For some absolute constant $ϵ>10^{-36}$, the max entropy algorithm outputs a TSP tour with expected cost at most $3/2-ϵ$ times the cost of $x$. Therefore the integrality gap of the subtour elimination LP is at most $3/2-ϵ$.”

• <a id="VVBM2025"></a>[VVBM2025] Villa, Tullio; Vercesi, Eleonora; Barta, Janos; Mastrolilli, Monaldo. The Integrality Gap of the Traveling Salesman Problem is $4/3$ if the LP Solution Has at Most $n+6$ Non-zero Components. arXiv preprint 2507.07003. arXiv PDF: 2507.07003. Google Scholar
• <a id="VVBM2025-nplus6"></a>[VVBM2025-nplus6] loc: arXiv PDF p. 1, Abstract, file arXiv:2507.07003 PDF quote: “Abstract. We address the classical Dantzig–Fulkerson–Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be $4/3$. We prove that, when solving a problem on $n$ nodes, if the optimal SEP solution has at most $n+6$ non-zero components, then the conjecture is true.”

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.