SFU Theory Seminar Series: Nathan Klein

  • Date: 02/10/2020
  • Time: 11:30
Nathan Klein, UW

Simon Fraser University


An Improved Approximation Algorithm for TSP in the Half Integral Case


The traveling salesperson problem (TSP) is one of the most celebrated and well-studied NP-complete problems we know. A classic result from Christofides in the 70s tells us that a fast algorithm exists which returns a solution at most 3/2 times worse than the optimal. Since then, however, no better approximation algorithm has been found, and improving upon it has become a famous open problem in theoretical computer science. In this talk, I will give an overview of research towards this goal and will present the first sub-3/2 approximation algorithm for an interesting special case, so-called "half integral" TSP instances. Despite their simple structure, Schalekamp, Williamson and van Zuylen conjecture that these are "the hardest" instances of TSP to approximate. This presentation is of joint work with Anna Karlin and Shayan Oveis Gharan.

Other Information: 

Location: SFU Burnaby, CS-Seminar room [9204]