Metric TSP subtour integrality gap

Four cities have travel cost 1 between every pair. A route visiting each city once and returning to its start uses four connections and costs 4. A cheaper-to-compute model can assign fractions to connections instead of choosing a real route: taking two thirds of every one of the six connections also costs 4 and passes the model’s rules. In general that fractional model can cost less than any route. For symmetric travel costs obeying the triangle inequality—going directly never costs more than going through a third city—can the cheapest real route always cost at most one third more than the best fractional value?[1] [3]

Can fractional route constraints always guarantee a real tour costing at most $4/3$ of their minimum cost? Costs are nonnegative and symmetric, and obey the triangle inequality: going directly never costs more than going through a third city. Consider two groups of three cities, $A_1,A_2,A_3$ and $B_1,B_2,B_3$. Distances within either group are 2; matched pairs $A_iB_i$ cost 1, and other cross-group pairs cost 3. These are shortest-path distances in two cost-2 triangles joined by cost-1 matched edges, so they obey the triangle inequality. Assign amount 1 to each matched edge, $1/2$ to each triangle edge and zero to the other edges. Each city's incident total is two; every proper nonempty cut has amount at least two. The fractional cost is 9, while the cheapest tour costs 10.

In general let $c_e$ be a connection’s cost and $x_e$ its chosen amount. For every city $v$, its touching connections must total two. Minimize $\sum_e c_ex_e$ subject to $\sum_{e\ni v}x_e=2$, $\sum_{e\in\delta(S)}x_e\ge2$ for every proper nonempty $S$, and $x_e\ge0$. Here $\delta(S)$ means edges crossing from $S$ to its complement.[1] [3]

The fractions on connections touching each city must add to two. Across every division into two nonempty groups, the crossing connections must also have total weight at least two. Those are route-like checks, but the fractions need not describe one actual route. Families of examples approach a real-to-fractional cost ratio of 4/3; a matching upper bound for every allowed instance is not known.[1] [2] [3]

In the six-city illustration each city has only one cost-1 connection; its amount is at most one by the degree and cut constraints. The remaining incident amount costs at least 2 per unit, giving fractional cost at least 9, attained above. A tour of cost 10 is $A_1,A_2,A_3,B_3,B_2,B_1,A_1$. Exact enumeration confirms no cheaper tour, so this example has ratio $10/9$, not $4/3$. The general gap is the supremum of $\mathrm{OPT}/\mathrm{LP}$ over the scoped instances with $\mathrm{LP}>0$. Song's September 2026 preprint reports an improved upper bound below $3/2$ but still above $4/3$; it remains a preprint claim.[1] [2] [3]

The fractional value is a lower bound on the cheapest real route. If it is 1000 and a route costs 1100, that route is at most 10% above the true optimum, even if the optimum is unknown. Understanding the worst possible gap tells us how much information this computable certificate can provide, and when apparently strong local route checks still miss a global routing cost.[1] [3]

A tour is an integral solution of the relaxation: choosing its edges as amounts 1 satisfies the degree and cut conditions. Thus $\mathrm{LP}\le\mathrm{OPT}$, and any candidate route with cost $T$ has approximation ratio at most $T/\mathrm{LP}$. Proving $\mathrm{OPT}\le(4/3)\mathrm{LP}$ would establish the best possible universal strength of this lower bound. It would be an existence guarantee for a sufficiently cheap tour, not by itself a polynomial-time procedure to find one. The same tension between local fractional constraints and a coherent global discrete object recurs throughout combinatorial optimization.[1] [3]