We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and V\'egh. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from $506$ to $22+\epsilon$ for any $\epsilon > 0$. This also improves the upper bound on the integrality ratio from $319$ to $22$.
翻译:我们重新审视斯文松、塔尔纳夫斯基和V\'egh对不对称旅行推销员问题的常量系数近似算法。 我们改进了这一算法的每一个部分。 我们避免了减少为不可减少的情况,从而更简单、更佳地减少了脊椎动物夫妇的数量。 我们还表明,脊椎动物夫妇的算法的微小变种近似比率要小得多。 总的来说,我们把任何一美元 > 0美元的近似比率从506美元提高到22欧元。 这也将整体比率的上限从319美元提高到22美元。