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

List of contents

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.

About the author

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.Jens Vygen has been Professor at the University of Bonn since 2003. His work comprises many aspects of combinatorial optimization and its applications, notably to chip design and vehicle routing. He has co-authored two textbooks, organized several workshops and conferences, and has been co-editor of several scientific journals and books. He is a member of the Hausdorff Center for Mathematics.

Product details

• Authors: Vera Traub, Vera (University of Bonn) Vygen Traub, Jens Vygen, Vygen Jens
• Publisher: Cambridge University Press ELT
• Languages: English
• Product format: Hardback
• Released: 01.12.2024
• EAN: 9781009445412
• ISBN: 978-1-0-0944541-2
• No. of pages: 444
• Subjects: Natural sciences, medicine, IT, technology > Mathematics > Miscellaneous; World, Optimization, MATHEMATICS / Optimization, MATHEMATICS / Discrete Mathematics, COMPUTERS / Programming / Algorithms, 21st Century, 21st century, c 2000 to c 2100, c 1500 onwards to present day, algorithms and data structures, Discrete Mathematics, Algorithms & data structures, Maths for computer scientists, Modern Period, C 1500 Onwards, For undergraduate education and equivalents, For graduate / post-graduate and equivalents