A constant-factor approximation algorithm for the asymmetric traveling salesman problem

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.

Authors

• Ola Svensson
• Jakub Tarnawski
• László A. Végh

Keywords

• linear programming
• approximation algorithms
• combinatorial optimization
• asymmetric traveling salesman problem