Spring 2019

A (Slightly) Improved Approximation Algorithm for Metric TSP

Friday, September 11th, 2020 9:00 am9:50 am

Add to Calendar


Nathan Klein (University of Washington)

In this talk, I will describe recent work in which we obtain a 3/2-epsilon approximation algorithm for metric TSP, for some epsilon > 10^{-36}. This slightly improves over the classical 3/2 approximation algorithm due to Christofides [1976] and Serdyukov [1978] . The talk will give an overview of the key ideas involved, with a particular focus on our use of the properties of Strongly Rayleigh distributions. This is joint work with Anna Karlin and Shayan Oveis Gharan.