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
14 - Symmetric Path TSP and T-Tours
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
Like in the asymmetric case (cf. Chapter 9), one can consider the generalization of Symmetric TSP where the start and end of the tour that we are looking for are not necessarily identical. Christofides’ algorithm can be generalized to this problem but only yields a 5/3-approximation here.
This chapter contains basic results about this problem and also a further generalization called T-tours; these results will be used in subsequent chapters where we will present better approximation algorithms. One important observation is that the "narrow cuts" of an LP solution have a nice structure.
For unweighted graphs, a 3/2-approximation algorithm can be obtained with the techniques of Chapter 13, or with a simple LP-based approach that we will present in this chapter.
- Type
- Chapter
- Information
- Approximation Algorithms for Traveling Salesman Problems , pp. 303 - 323Publisher: Cambridge University PressPrint publication year: 2024