Id: arxiv/2611.09421 Url: https://arxiv.org/abs/2611.09421 Tags: cs.DS, cs.CC, math.OC Score: 0 Title: Improved Approximation and Hardness Bounds for $β$-TSP Domain: cs.DS Source: arxiv Authors: Paul Liu, Jack Spalding-Jamieson, Da Wei Zheng Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-06 Page: https://delphi.science/r/arxiv/2611.09421 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 $β$-TSP, where the edge lengths satisfy $ \ell_{uw}\leqβ(\ell_{uv}+\ell_{vw}) \qquad \forall\,u,v,w\in V\ \text{pairwise distinct}, \quad β\in\left[\tfrac{1}{2},1\right]. $ The condition arises naturally in various…