摘要
我们提出了几种有界度旅行商问题的改进算法。在有界度旅行商路径问题 (BDTSPP) 中，给定一个加权图 $G=(V,E)$，两个端点 $s$ 和 $t$，以及所有顶点 $v$ 的度界限 $b_v$，目标是找到一个代价最小的 $G$ 的子图，该子图支持一个欧拉 $s$-$t$ 路径，并且每个顶点 $v$ 的度不超过 $b_v$。
由于判定可行性已经是 NP-hard 问题，之前的工作提供了一种双标准近似算法。然而，该算法仅对度的违规提供了乘法保证，是否可能实现加法违规仍然悬而未决。我们通过提出一种新的双标准近似算法，给出了积极的答案，允许加法度违规。同时，成本近似比也得到了改善，现在与 Hoogeveen 对 Christofides-Serdyukov 算法的分析相匹配。
这一改进依赖于一个新的引理，使得可以使用有界度最小生成树，而不是有界度斯坦纳树，作为算法的起点。该引理比较了树的成本和度数与当前有界度 TSP 的整数最优解，而不是与分数最优解的比较。
此外，我们的引理也为电路版本 (BDTSP) 带来了改进：我们给出了一个双标准算法，匹配之前的成本近似比，同时将加法度违规减少到 +2，这是最佳可能的。有界度子集 TSP 是标准“全顶点” TSP 的推广，其中仅需访问指定的顶点子集。我们为电路和路径版本都提出了改进。
对于子集路径问题 (BDSTSPP)，我们提出了第一个具有加法度违规的双标准近似算法；对于子集电路问题 (BDSTSP)，我们给出了改进的成本近似比。
博主点评： 本文在有界度旅行商问题上提出了重要的算法改进，尤其是通过引入新的引理显著提高了近似效果。该研究不仅填补了理论上的空白，同时为实际应用中的图优化问题提供了新的解决思路，具有广泛的应用前景。