旅行商问题（TSP）要求在完全加权图中找到最短的哈密顿环。其可近似性取决于边长的约束：
- 任意实例在 (\mathrm{P}\neq\mathrm{NP}) 时不存在常数因子近似；
- 度量实例可通过 Christofides 算法得到 $3/2$ 近似；
- 固定维欧几里得实例拥有 PTAS。
本文研究的 (\beta)-TSP 令所有不同顶点 @@@MATH_BLOCK1@@@ 满足 $$ \ell{uw}\le \beta\bigl(\ell{uv}+\ell{vw}\bigr),\qquad \beta\in\bigl[\tfrac12,1\bigr]. $$ 该不等式自然出现于将度量旅行时间与顶点正服务时间相加的情形。此前 B\"ockenhauer 等人的算法在 (\beta=\tfrac12) 时恰好达到 $1$，而当 (\beta\to1) 时上界为 $3/2$。
我们提出的算法在整个区间 $[\tfrac12,1]$ 上均严格优于上述结果。核心思路是：
- 先构造满足 (\beta) 条件的最小生成树（MST），
- 对奇度顶点做最小权匹配，
- 合并得到欧拉回路并进行路径拆分。 在匹配阶段引入了基于 (\beta) 的加权修正，使得匹配成本相对于 MST 的比例始终低于 $\frac{\beta}{2\beta-1}$，从而整体近似因子为 $$\alpha(\beta)=\frac{2\beta}{2\beta-1}\in\bigl(1,\tfrac32\bigr].$$ 当 (\beta=\tfrac12) 时 $\alpha=1$，随 (\beta) 增大而单调上升，且在 (\beta=1) 时恰为 $3/2$，与 Christofides 的上界一致但在所有中间值上更紧。
在硬度方面，我们通过对称性约束的归约证明了在任意 (\beta>\tfrac12) 时，(\beta)-TSP 至少与一般 TSP 同样难以在 $1+\epsilon$ 因子下近似（除非 (\mathrm{P}=\mathrm{NP})），并给出基于 PCP 的 $\frac{\beta}{2\beta-1}$ 下界。
综上，本文在近似上实现了对所有合法 (\beta) 的统一改进，并给出了相匹配的硬度下界，填补了此前算法与理论之间的空白。
点评：该工作通过细致的匹配加权技巧，将 (\beta)-TSP 的近似因子紧密绑定于参数本身，实现了从 $1$ 到 $3/2$ 的平滑提升，同时提供了相应的不可突破下界，具有重要的理论价值和潜在的实际应用前景。