CombOpt Reading Group | Mehrdad Sohrabi, Approximating graphic TSP by b-matchings

Abstract: We are going to talk about approximating graphic TSP, which is a variant of TSP where the distances come from shortest paths between vertices of an undirected graph. We will talk about Mömke and Svensson’s approach, which used matchings to improve the approximation ratio, and also our recent generalization that uses b-matchings. This is joint work with Levent Tunçel and Swati Gupta.