Friday, January 10, 2020 1:00 pm
-
1:00 pm
EST (GMT -05:00)
Title: Beating 3/2 for Approximating TSP in the Half-Integral Case
| Speaker: | Logan Grout |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
In 2013, Schalekamp, Williamson, and van Zuylen conjectured that the integrality gap for the Subtour Polytope was attained on its half-integral vertices.In 2019, Karlin, Klein, and Oveis Gharan published a paper on Arxiv in which they describe a randomized polytime algorithm that, when given half-integral solution to the Subtour LP, produces a tour of cost at most 1.49993 times the cost, beating the 1.5-approximation guarantee of Christofides' algorithm. In this talk, we will discuss the key tools used in the design and analysis of this new algorithm.