Book contents
- Frontmatter
- Preface
- Contents
- 1 Introduction
- 2 Linear Programming Relaxations of the Symmetric TSP
- 3 Linear Programming Relaxations of the Asymmetric TSP
- 4 Duality, Cuts, and Uncrossing
- 5 Thin Trees and Random Trees
- 6 Asymmetric Graph TSP
- 7 Constant-Factor Approximation for the Asymmetric TSP
- 8 Algorithms for Subtour Cover
- 9 Asymmetric Path TSP
- 10 Parity Correction of Random Trees
- 11 Proving the Main Payment Theorem for Hierarchies
- 12 Removable Pairings
- 13 Ear-Decompositions, Matchings, and Matroids
- 14 Symmetric Path TSP and T-Tours
- 15 Best-of-Many Christofides and Variants
- 16 Path TSP by Dynamic Programming
- 17 Further Results, Related Problems
- 18 State of the Art, Open Problems
- Bibliography
- Index
15 - Best-of-Many Christofides and Variants
Published online by Cambridge University Press: 14 November 2024
- Frontmatter
- Preface
- Contents
- 1 Introduction
- 2 Linear Programming Relaxations of the Symmetric TSP
- 3 Linear Programming Relaxations of the Asymmetric TSP
- 4 Duality, Cuts, and Uncrossing
- 5 Thin Trees and Random Trees
- 6 Asymmetric Graph TSP
- 7 Constant-Factor Approximation for the Asymmetric TSP
- 8 Algorithms for Subtour Cover
- 9 Asymmetric Path TSP
- 10 Parity Correction of Random Trees
- 11 Proving the Main Payment Theorem for Hierarchies
- 12 Removable Pairings
- 13 Ear-Decompositions, Matchings, and Matroids
- 14 Symmetric Path TSP and T-Tours
- 15 Best-of-Many Christofides and Variants
- 16 Path TSP by Dynamic Programming
- 17 Further Results, Related Problems
- 18 State of the Art, Open Problems
- Bibliography
- Index
Summary
An, Kleinberg, and Shmoys were the first to beat Christofides’ algorithm for Path TSP. Their algorithm, which they called Best-of-Many Christofides, is very natural: Since an LP solution can be written as convex combination of spanning trees, we can do parity correction on each of these trees and output the best of the resulting tours. It turns out that this yields a better guarantee than the 5/3 that Christofides’ algorithm yields.
In this chapter, we analyze this algorithm and study various follow-up works that have yielded better and better approximation ratios; some of them also apply to general T-tours. This includes a structured decomposition into spanning trees (by Gottschalk and Vygen), Best-of-Many Christofides with lonely edge deletion (by Sebő and van Zuylen), and Traub’s T-tour algorithm.
- Type
- Chapter
- Information
- Approximation Algorithms for Traveling Salesman Problems , pp. 324 - 350Publisher: Cambridge University PressPrint publication year: 2024