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, self-study, and further research.
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, self-study, and further research.
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.
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.
Es gelten unsere Allgemeinen Geschäftsbedingungen: www.buecher.de/agb
Impressum
www.buecher.de ist ein Shop der buecher.de GmbH & Co. KG Bürgermeister-Wegele-Str. 12, 86167 Augsburg Amtsgericht Augsburg HRA 13309
