A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

  • Jakub Tarnawski | Theory of Computation laboratory at the EPFL

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. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. This is joint work with Ola Svensson and László Végh.

Speaker Details
Doctoral Student Jakub Tarnawski
Jakub Tarnawski is a doctoral student in the Theory of Computation laboratory at the EPFL, under the guidance of Ola Svensson. He obtained his MSc in Mathematics and Computer Science from the University of Wrocław, Poland. He is broadly interested in theoretical computer science and combinatorial optimization, particularly in graph algorithms and approximation algorithms. He has received “Best paper” awards at FOCS 2017 and STOC 2018 for his work on matchings and the traveling salesman problem, respectively.

Series: Microsoft Research Talks