n this extended abstract, we survey some of the recent results on approximating the traveling salesman problem on graphic metrics.

We start by briefly explaining the algorithm of Oveis Gharan et al. [1] that has strong similarities to Christofides’ famous 3/2-approximation algorithm. We then explain the main ideas behind an alternative approach introduced by Mömke and the author [2]. The new ingredient in our approach is that it allows for the removal of certain edges while simultaneously yielding a connected, Eulerian graph, which in turn leads to a decreased cost. We also overview the exciting developments for TSP on graphic metrics that rapidly followed: an improved analysis of our algorithm by Mucha [3] yielding an approximation guarantee of 1.44, and the recent developments by Sebö and Vygen [3] who gave a 1.4-approximation algorithm.

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