An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
Vera Traub, Jens Vygen · SIAM Journal on Computing · 2022
We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and Végh [ J. ACM, 67 (2020), 37]. 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.