{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-06","reactions":{}}