Nathan Klein: A (Slightly) Improved Approximation Algorithm for Metric TSP

Tuesday, October 27, 2020 - 4:00pm to 5:15pm
Location: 
Zoom Link: https://mit.zoom.us/meeting/register/tJIlceuqrzMoGdyQJAyITXLXnN6t5C1ZEDnf
Speaker: 
Nathan Klein
Seminar group: 
Theory of Computation (TOC) Seminar
Abstract: 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 focus on giving an overview of the key ideas involved. This is joint work with Anna Karlin and Shayan Oveis Gharan.