{"id":"palomar/PALOMAR-2026-09-26-000005","url":"https://github.com/troyjlee/tcs-formalizations/tree/55d7c9c11ee4240328a71b1ab43d66f27a976da6","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-09-26-000005-v1.json","repo":"https://github.com/troyjlee/tcs-formalizations","tags":["cs.DS","math.CO","msc:90C27","msc:05C45","combinatorial-optimization","tsp","lean-formalization","approximation"],"score":0,"title":"Metric TSP subtour-LP integrality gap","trust":"high","domain":"cs.DS","source":"palomar","authors":["Troy Lee"],"reviews":0,"subject":"cs.DS","summary":"Lean proofs that every metric TSP instance on at least three vertices has a Hamiltonian tour costing at most (3/2 - 2.05522e-30) times any feasible subtour-LP objective, with one strictly larger saving uniform over all instances. The submission also exposes the exact finite-layer saving and a KKO-framework bound using GKL capacity estimates.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-09-26","reactions":{},"formalized":true,"formalizes":[{"title":"A (Slightly) Improved Approximation Algorithm for Metric TSP","identifier":"https://arxiv.org/abs/2007.01409v6","relationship":"adapts"},{"title":"A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP","identifier":"https://arxiv.org/abs/2105.10043v3","relationship":"adapts"},{"title":"From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP","identifier":"https://arxiv.org/abs/2311.09072v2","relationship":"adapts"},{"title":"A Sharper Explicit Bound on the Subtour-LP Integrality Gap for Metric TSP","identifier":"https://www.preprints.org/manuscript/202609.0140/v1","relationship":"adapts"}]}