Recently, a number of results appeared that give improved bounds for a Christofides-like algorithm for the s-t path TSP, in an attempt to lower the approximation ratio from 5/3 to the conjectured integrality gap of 3/2. We give a much simpler framework for analyzing these "best-of-many" Christofides algorithms, and we introduce a key new idea of deleting edges from the initial trees. We show that the arising connectivity problems can be solved for a minor extra cost, thus allowing us to more than halve the gap between the best known ratio and the conjectured integrality gap of 3/2.

(Joint work with Andras Sebo.)