Talks
Spring 2019
A (Slightly) Improved Approximation Algorithm for Metric TSP
Friday, September 11th, 2020, 9:00 am–9:50 am
Speaker:
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.