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
8 - Algorithms for Subtour Cover
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
In this chapter, we will present an algorithm for the subtour cover problem, which we defined in Chapter 7. This will complete the constant-factor approximation algorithm for the Asymmetric TSP.
The subtour cover problem was introduced (in a slightly different form) by Svensson, Tarnawski, and Végh, who gave a (4,2,1)-algorithm for subtour cover. Traub and Vygen strengthened this to a (3,2,1)-algorithm. Here, we further improve this to a (2,2,1)-algorithm. Our subtour cover algorithm builds on the algorithm for the graph subtour cover problem that we presented in Section 6.2.
As a final result, we obtain a (17+ε)-approximation for the Asymmetric TSP for any fixed ε>0.
- Type
- Chapter
- Information
- Approximation Algorithms for Traveling Salesman Problems , pp. 159 - 182Publisher: Cambridge University PressPrint publication year: 2024