Sharper bound improves approximation for metric traveling salesman problem
A Sharper Explicit Bound on the Subtour-LP Integrality Gap for Metric TSP
Data Structures and Algorithms
Summary
The traveling salesman problem asks how to find the shortest route visiting many places once and returning home. This paper improves the known guarantee for a popular mathematical method used to approximate answers to this problem, showing it is slightly better than previously proven. The authors build on earlier work that gave tiny improvements and make the improvement much clearer and larger, though it is still very small compared to the best possible. This helps to understand how close these methods can get to the true best solution.
What this means in practice
- •For logistics planners: Use the paper's improved guarantees to better assess solution quality when routing delivery vehicles with metric constraints.
- •For transportation schedulers: Incorporate enhanced approximation bounds to improve route planning estimates in systems modeled by metric traveling salesman problems.
A theory result. No direct application yet.
Authors
Zhao Song
Abstract
Karlin, Klein, and Oveis Gharan introduced a randomized better-than-$3/2$ approximation algorithm for metric TSP [KKO21] and subsequently established the corresponding improvement in the integrality gap of the subtour-elimination LP [KKO22], with an explicit constant $\varepsilon>1.00000\cdot10^{-36}$. Gurvits, Klein, and Leake subsequently improved the certified saving to $2.18000\cdot10^{-34}$ [GKL24]. In this paper, we obtain a randomized polynomial-time $(3/2-\varepsilon)$-approximation for every fixed $0<\varepsilon<\varepsilon_\star$, where $\varepsilon_\star>2.78621\cdot10^{-18}$, and consequently the subtour-elimination LP has integrality gap at most $3/2-\varepsilon_\star$. The classical worst-case integrality-gap lower bound is $4/3$ [Wil90].