Publication
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). 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.
Ali H. Sayed, Stefan Vlaski, Elsa Rizk
Michel Bierlaire, Fabian Alejandro Torres Duran, Tom Haering
Christophe Ballif, Nicolas Würsch, Laure-Emmanuelle Perret Aebi, Marine Dominique Cauz