The traveling salesman problem (TSP) asks for a minimum‑length Hamiltonian cycle in a complete weighted graph. Its approximability depends on edge‑length constraints:
- Unrestricted instances admit no constant‑factor approximation unless (\mathrm{P}=\mathrm{NP});
- Metric instances admit Christofides’ $3/2$‑approximation;
- Fixed‑dimensional Euclidean instances admit a PTAS.
We study (\beta)-TSP, where for any three distinct vertices @@@MATH_BLOCK1@@@ the edge lengths satisfy $$ \ell{uw}\le \beta\bigl(\ell{uv}+\ell{vw}\bigr),\qquad \beta\in\bigl[\tfrac12,1\bigr]. $$ This condition naturally arises when metric travel times are combined with positive service times at vertices. The previous best algorithm by B\"ockenhauer et al. yields a guarantee of $1$ at $\beta=\tfrac12$ and approaches $3/2$ as $\beta\to1$.
Our algorithm strictly improves the guarantee for every $\beta\in[\tfrac12,1]$. The main steps are:
- Build a minimum spanning tree (MST) that respects the $\beta$‑condition;
- Compute a minimum‑weight matching on the odd‑degree vertices, applying a $\beta$‑dependent weight adjustment;
- Merge the MST and matching into an Eulerian tour and shortcut to obtain a Hamiltonian cycle. The adjusted matching cost is bounded by $\frac{\beta}{2\beta-1}$ times the MST cost, leading to an overall approximation factor $$\alpha(\beta)=\frac{2\beta}{2\beta-1}\in\bigl(1,\tfrac32\bigr].$$ When $\beta=\tfrac12$, $\alpha=1$; as $\beta$ grows, $\alpha$ increases monotonically, reaching $3/2$ at $\beta=1$, matching Christofides’ bound but tighter for all intermediate values.
On the hardness side, we reduce from the general TSP to show that for any $\beta>\tfrac12$, achieving a $(1+\epsilon)$‑approximation is NP‑hard unless (\mathrm{P}=\mathrm{NP}). Moreover, a PCP‑based reduction yields a lower bound of $\frac{\beta}{2\beta-1}$ on the achievable approximation ratio.
In summary, we provide a unified improvement over the entire feasible $\beta$ range and a matching hardness lower bound, closing the gap between algorithmic performance and theoretical limits.
Review: The paper leverages a refined matching weighting technique to tightly couple the approximation ratio with the $\beta$ parameter, achieving a smooth transition from exactness at $\beta=1/2$ to the classic $3/2$ bound at $\beta=1$. The accompanying hardness results reinforce the optimality of the approach, offering both theoretical insight and practical relevance.