Approximating Graphic TSP by Matchings



Ola Svensson, EPFL

Monday, April 2, 2012
4:00 PM,
5130 Upson Hall



We will discuss a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost.

We then overview the exciting and rapid development for TSP on graphic metrics following this approach: our 1.461-approximation algorithm, the better analysis by Mucha'11 yielding an approximation guarantee of 1.44, and the recent development by Sevo & Vygen'12 who gave a 1.4-approximation algorithm.

Finally, we point out some interesting open problems where our techniques currently fall short from generalizing to more general metrics.