Towards Improving Christofides Algorithm on Fundamental Classes by Gluing Convex Combinations of Tours

Arash Haddadan, Alantha Newman

We present a new approach for gluing tours over certain tight, 3-edge cuts. Gluing over 3-edge cuts has been used in algorithms for finding Hamilton cycles in special graph classes…