10 - Parity Correction of Random Trees

Summary

The random sampling approach described in Chapter 5 for the Asymmetric TSP has also been used successfully for the Symmetric TSP. First, Oveis Gharan, Saberi, and Singh obtained the first algorithm with approximation ratio less than 3/2 for Graph TSP. More recently, Karlin, Klein, and Oveis Gharan proved that essentially the same algorithm has approximation ratio less than 3/2 for the general Symmetric TSP.

The algorithm is simple, but its analysis is very complicated. While for Graph TSP we know simpler and better algorithms today (see Chapters 12 and 13), the random sampling algorithm is still the best-known approximation algorithm for Symmetric TSP.

The algorithm samples a spanning tree from an (approximately) marginal-preserving λ-uniform distribution and then proceeds with parity correction like Christofides’ algorithm. After briefly discussing the analysis for Graph TSP, we present the first part of the analysis by Karlin, Klein, and Oveis Gharan, with some simplifications suggested by Drees. The main point is to reduce the set of relevant cuts that need to be considered to bound the cost of parity correction and obtain a nice structure that will be exploited in Chapter 11.