Abstract
Recent years have shown remarkable progress in the design and analysis of approximation algorithms for the graphical metric TSP and the general metric case of the s-t-path TSP. We will survey a number of these results, focusing in particular on the s-t-path TSP, where these results have seen the improvements to Christifides' algorithm yield a performance guarantee essentially matching the integrality gap of the standard LP relaxation.