Metric TSP subtour-LP integrality-gap constant

Upper bound, last-listed row

| $3/2 - 2.18 \cdot 10^{-34}$ | [[GKL2024](#GKL2024)] | Applying the stated LP-relative guarantee to an optimal subtour-LP solution yields the best currently established general upper bound. [GKL2024-ub-2p18e-34] |

exact pinned row

| $3/2 - 2.18 \cdot 10^{-34}$ | [[GKL2024](#GKL2024)] | Applying the stated LP-relative guarantee to an optimal subtour-LP solution yields the best currently established general upper bound. <a href="#GKL2024-ub-2p18e-34">[GKL2024-ub-2p18e-34]</a> |

tracked since 2026-07-24 — no movement seen yet

Lower bound, last-listed row

| $4/3$ | [[Hou2014](#Hou2014)] | Classical asymptotic lower bound: there exists a family of metric TSP instances whose integrality ratios converge to $4/3$. [Hou2014-gap-4over3] |

exact pinned row

| $4/3$ | [[Hou2014](#Hou2014)] | Classical asymptotic lower bound: there exists a family of metric TSP instances whose integrality ratios converge to $4/3$. <a href="#Hou2014-gap-4over3">[Hou2014-gap-4over3]</a> |

tracked since 2026-07-24 — no movement seen yet

Checked against material for its cited source

• The row shown above: bound row $4/3$ line 52 citing [Hou2014] — the claim we checked: that the cited 2014 paper gives the lower bound 4/3 through a family of metric TSP instances whose integrality ratios converge to 4/3, as the row's comment says. The row's second link, [Hou2014-gap-4over3], is checked only for whether it points at that statement. What we read supports it: the paper states that the integrality ratio of the subtour LP is at least 4/3 because a family of metric TSP instances has integrality ratios converging to 4/3, citing Williamson's 1990 thesis for it, and the row's second link points at that sentence. source link (read in arXiv version 3, the version the reference entry links, pp. 1–8, 10 and 11 as page images; the journal edition the entry also cites, Operations Research Letters 42 (2014), pp. 495–499, was not reached). Selected: drawn by its position in the list of cited rows, not because it looked wrong.

1 bound row(s) here have been checked against material for their cited source (1 drawn by position, 0 chosen because something already looked wrong). Across this whole ledger 70 row(s) have been drawn by position, against 691 rows that name a source, counted on 2026-09-27: 64 were checked against material for their cited sources and for 6 the cited source could not be read at all. 5 more were chosen for suspicion and checked; they are counted apart, because a set selected for suspicion carries no rate. A row not listed here has NOT been checked.