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
13 - Ear-Decompositions, Matchings, and Matroids
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
By combining the removable pairing technique presented in Chapter 12 with a new approach based on ear-decompositions and matroid intersection, Sebő and Vygen improved the approximation ratio for Graph TSP from 13/9 to 7/5. We will present this algorithm, which is still the best-known approximation algorithm for Graph TSP, in this chapter.
An interesting feature of this algorithm is that it is purely combinatorial, does not need to solve a linear program, and runs in O(n3) time. To describe the algorithm, we review some matching theory, including a theorem of Frank that links ear-decompositions to T-joins. A slight variant of the Graph TSP algorithm is a 4/3-approximation algorithm for finding a smallest 2-edge-connected spanning subgraph, which was the best known for many years. The proofs will also imply corresponding upper bounds on the integrality ratios.
- Type
- Chapter
- Information
- Approximation Algorithms for Traveling Salesman Problems , pp. 280 - 302Publisher: Cambridge University PressPrint publication year: 2024