AN IMPROVED APPROXIMATION ALGORITHM FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM.

We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and V\'egh [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 + ε for any ε > 0. This also improves the upper bound on the integrality ratio from 319 to 22. [ABSTRACT FROM AUTHOR]