Jakub Tarnawski: Approximation Algorithms for the (Asymmetric) Traveling Salesman Problem

The famous Traveling Salesman Problem (TSP) asks: given a graph with weights on edges, what is the shortest tour that visits all vertices? As TSP is NP-hard, the theoretical study of algorithms for TSP has focused on approximation algorithms - ones that are provably both efficient and give solutions competitive with the optimum. In this talk I will give a short introduction to approximation algorithms for TSP. In particular, I will discuss the first constant-factor approximation algorithm for the asymmetric version of TSP (ATSP), where the graph is directed, which is a 2017 joint work with Ola Svensson and László Végh. This will serve as a nice example of how linear programming is a very useful technique in the design of algorithms for discrete problems.