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
5 - Thin Trees and Random Trees
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
After the O(log n)-approximation algorithms for Asymmetric TSP, the first algorithm to beat the cycle cover algorithm by more than a constant factor was found in 2009 by Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi. Their approach is based on finding a "thin" (oriented) spanning tree and then adding edges to obtain a tour. A major open question is how thin trees are guaranteed to exist.
The O(log n/loglog n)-approximation algorithm by Asadpour et al. samples a random spanning tree from the maximum entropy distribution. To show how this works, we discuss interesting connections between random spanning trees and electrical networks. Some results of this chapter will be used again in Chapters 10 and 11.
- Type
- Chapter
- Information
- Approximation Algorithms for Traveling Salesman Problems , pp. 87 - 113Publisher: Cambridge University PressPrint publication year: 2024