Approximation Algorithms for the Asymmetric Traveling Salesman Problem
The talk will give an overview on recent developments on the asymmetric traveling salesman problem (ATSP). In contrast to the symmetric problem variant, where the Christofides-Serdyukov algorithm gives a simple 3/2-approximation, no constant-factor approximation algorithm has been known for a long time. The talk will give an overview of the different approaches that have lead to improved approximation guarantees over the last decade. I will present the approach of our paper with Svensson and Tarnawski that led to the first constant factor approximation guarantee in 2017, and a subsequent improvement by Traub and Vygen.