Talk: A (Slightly) Improved Approximation Algorithm for Metric TSP

LIVE STREAM:  https://uwmadison.zoom.us/j/98942632371?pwd=TTNsNmVRcGtPWTdENW5IelFoODNMdz09

Abstract: In the metric traveling salesperson problem (TSP) we are given a list of cities and their pairwise symmetric distances, which form a metric. Our goal is to find the shortest tour that visits every city exactly once. The problem is NP-Hard, and therefore it is unlikely that an efficient algorithm exists which can solve it exactly. However, in 1976 Christofides gave a beautiful 3/2 approximation algorithm for the problem, meaning a polynomial time algorithm which provably returns a tour at most 50% longer than the optimal one. This algorithm is one of the first approximation algorithms ever designed and is routinely used in practice for planning and routing tasks. In this talk I will describe an approximation algorithm for TSP with approximation ratio below 3/2, representing the first improvement in nearly half a century.

Bio: Nathan Klein is a final year Ph.D. student at the University of Washington where he is advised by Anna Karlin and Shayan Oveis Gharan. His primary research interest is studying approximation algorithms for classical optimization problems. He has received a best paper award at STOC 2021 and an NSF GRFP fellowship for his work on the traveling salesperson problem.