Vera Traub, Jens Vygen

Approximation Algorithms for Traveling Salesman Problems

• Gebundenes Buch

Produktbeschreibung

"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"--

---

Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.

Produktdetails

• Verlag: Cambridge University Press
• Seitenzahl: 442
• Erscheinungstermin: 5. Dezember 2024
• Englisch
• Abmessung: 235mm x 157mm x 28mm
• Gewicht: 787g
• ISBN-13: 9781009445412
• ISBN-10: 1009445413
• Artikelnr.: 70600486

Autorenporträt

Vera Traub has been Professor at the University of Bonn since 2023. Her research has received multiple awards, particularly her work on approximation algorithms for network design and the traveling salesman problem, including in 2023 the Maryam Mirzakhani New Frontiers Prize and the Heinz Maier-Leibnitz Prize. She is a member of the Hausdorff Center for Mathematics.

Inhaltsangabe

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.