Skip to content
Preprint

Improved Approximation and Hardness Bounds for $\beta$-TSP

Nov 2026 · 0 citations · 21 references
Computer Science Mathematics

Abstract

The traveling salesman problem (TSP) asks for a minimum-length Hamiltonian cycle in a complete weighted graph. Its approximability depends on the edge lengths: unrestricted instances admit no constant-factor approximation unless $\mathrm{P}=\mathrm{NP}$, metric instances admit Christofides'$3/2$-approximation, and fixed-dimensional Euclidean instances admit a PTAS. We study $\beta$-TSP, where the edge lengths satisfy $ \ell_{uw}\leq\beta(\ell_{uv}+\ell_{vw}) \qquad \forall\,u,v,w\in V\ \text{pairwise distinct}, \quad \beta\in\left[\tfrac{1}{2},1\right]. $ The condition arises naturally in various settings, for example, when metric travel times are combined with positive service times at the vertices. The previous best approximation algorithm, due to B\"ockenhauer et al., ranges from $1$ at $\beta=1/2$ to $3/2$ as $\beta$ approaches $1$. We obtain a strictly better guarantee for every $1/2<\beta<1$ by combining two simple constructions whose guarantees counterbalance each other. We also improve the best known approximation hardness bound for every $1/2<\beta<1$.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.