TCS+ Talk

Abstract: A classic result from Christofides in the 70s tells us that a fast algorithm for the traveling salesperson problem (TSP) exists which returns a solution at most 3/2 times worse than the optimal. Since then, however, no better approximation algorithm has been found. In this talk, I will give an overview of research towards the goal of beating 3/2 and will present the first sub-3/2 approximation algorithm for the special case of "half integral" TSP instances. These instances have received significant attention in part due to a conjecture from Schalekamp, Williamson and van Zuylen that they attain the integrality gap of the subtour polytope. If this conjecture is true, our work shows that the integrality gap of the polytope is bounded away from 3/2, giving hope for an improved approximation for the general case. This presentation is of joint work with Anna Karlin and Shayan Oveis Gharan.

To watch the talk:

• Watching the live stream. At the announced start time of the talk (or a minute before), a live video stream will be available on our "next talk" page. Simply connect to the page and enjoy the talk. No webcam or registration is needed. Questions and comments during the talk are welcome (text only, unfortunately); simply post a comment below the live video stream on YouTube.
• Watching the recorded talk offline. The recorded talk will be made available shortly after the talk ends on our YouTube page. (Please leave a comment if you enjoyed it!)