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

Computer Science/Discrete Mathematics Seminar II
Topic:A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Speaker:Ola Svensson
Affiliation:École polytechnique fédérale de Lausanne
Date:Tuesday, January 23
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2018/0123-OlaSvensson

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 lecture aims to give a more detailed explanation of our approach. This is joint work with Jakub Tarnawski and László Végh.