In the symmetric metric traveling salesman problem, one is given a complete graph Kn=(V,E) with a nonnegative symmetric cost function c:E→R≥0 satisfying the triangle inequality. For S⊆V, let δ(S) denote the set of edges with exactly one endpoint in S, and write δ(v):=δ({v}). Let TSP(c) be the minimum cost of a Hamiltonian cycle in Kn. The subtour-elimination linear program has optimum value
SEP(c):=mine∈E∑cexe
subject to
e∈δ(v)∑xe=2for all v∈V,
e∈δ(S)∑xe≥2for all ∅⊊S⊊V,
xe≥0for all e∈E.
[KKO2022-metric-def] [KKO2022-lp-def]
We define
C75:=supSEP(c)TSP(c),
where the supremum ranges over all finite metric TSP instances. Equivalently, C75 is the worst-case integrality gap of the subtour-elimination LP for metric TSP.
[Hou2014-gap-4over3]
The best established range is
34≤C75≤23−2.18⋅10−34,
and the long-standing conjecture is that C75=34.
[Hou2014-gap-4over3] [GKL2024-ub-2p18e-34] [KKO2022-ub-eps]