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
6 - Asymmetric Graph TSP
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
A major step towards the first constant-factor approximation algorithm for the Asymmetric TSP was made by Svensson. He devised a constant-factor approximation algorithm for Asymmetric Graph TSP, which is the special case of the Asymmetric TSP with c(e)=1 for all e ∈ E.
In this chapter, we present Svensson’s algorithm for the Asymmetric Graph TSP. We also incorporate some improvements, from Traub and Vygen, who gave a variant of Svensson’s algorithm with improved approximation ratio. Moreover, we present an improved algorithm for finding a graph subtour cover, which is the main subroutine of Svensson’s algorithm. Overall, we will obtain an approximation ratio of 8+ε for Asymmetric Graph TSP, for every ε>0.
Almost all techniques presented in this chapter will be used again in Chapters 7 and 8 for the general Asymmetric TSP.
- Type
- Chapter
- Information
- Approximation Algorithms for Traveling Salesman Problems , pp. 114 - 133Publisher: Cambridge University PressPrint publication year: 2024