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
11 - Proving the Main Payment Theorem for Hierarchies
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
This chapter is about the proof of the main payment theorem for hierarchies by Karlin, Klein, and Oveis Gharan, a key piece of their better-than-3/2-approximation algorithm for Symmetric TSP. Because the proof is very long and technical, we will not give a complete proof here but rather focus on explaining the key combinatorial ideas.
This chapter is structured as follows. First, we describe the general proof strategy and prove the theorem in an idealized setting. Then we discuss a few crucial properties of λ-uniform distributions. The following sections focus on the main ideas needed to address the hurdles we ignored in the idealized setting described initially.
Finally, we show how the Karlin–Klein–Oveis Gharan algorithm can be derandomized.
- Type
- Chapter
- Information
- Approximation Algorithms for Traveling Salesman Problems , pp. 231 - 264Publisher: Cambridge University PressPrint publication year: 2024