ARC and Indo-US Virtual Center Seminar: Shayan Oveis Gharan (Univ. of Washington)

Algorithms & Randomness Center (ARC) and Indo-US Virtual Center Seminar

Shayan Oveis Gharan (University of Washington)

Monday, July 27, 2020

Virtual via Bluejeans - 11:30 am


Title:  A (slightly) Improved Approximation algorithm for Metric TSP

Abstract:  I will sketch some of the ideas in our recent 3/2-eps approximation algorithm for Metric TSP. The field of geometry of polynomials plays a fundamental role in our proof as we use and prove several (new) properties of strongly Rayleigh distributions.

Based on a joint work with Anna Karlin and Nathan Klein


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Event Details


  • Monday, July 27, 2020
    12:30 pm - 2:00 pm