Approximation Algorithms for Traveling Salesman Problems

"This is the first book on approximation algorithms for the Traveling Salesman Problem, a central topic in discrete mathematics, theoretical computer science, and combinatorial optimization. It presents the state of the art comprehensively as well as advances it, making it an excellent resource for teaching, selfstudy, and further research"--

Preface; 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.