Title: Approximating Graphic TSP with matchings
| Speaker: | Sina Kalantarzadeh |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: Revisiting defining character of the field of algorithm design and complexity, TSP!. While the problem itself is NP-Hard and difficult to approximate, various formulations, such as the Metric version, have yielded notable approximation algorithms. The classical 1.5-approximation algorithm by Christofides, leveraging matchings, stood as the best-known result for decades. However, recent breakthroughs have pushed these boundaries further.
In this talk, I will focus on the work of Mömke and Svensson(2011), who have improved the approximation factor for Graphic TSP to 1.461. Their method builds on the framework of Christofides’ algorithm but incorporates a more sophisticated use of matchings.
We mainly focus on exploring their algorithm within the instances of Graphic TSP, whose the degree of their corresponding graph is bounded degree by 3, where it achieves a remarkable 4/3 approximation factor matching the 4/3 conjecture. From there, we will extend the discussion to the instances with more generalized graph structures, illustrating how these innovative techniques enhance the approximation quality.