A constant-factor approximation algorithm for the asymmetric traveling salesman problem
Ola Svensson, Jakub Tarnawski, László A. Végh · 2018
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.