Papers for

transportation schedulers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Sharper bound improves approximation for metric traveling salesman problem

A Sharper Explicit Bound on the Subtour-LP Integrality Gap for Metric TSP

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].

Mon 28 SeptData Structures and Algorithms

The gist

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.

Open → 2609.34600v1