Our systems are now restored following recent technical disruption, and we’re working hard to catch up on publishing. We apologise for the inconvenience caused. Find out more

Recommended product

Popular links

Popular links


Approximation Algorithms for Traveling Salesman Problems

Approximation Algorithms for Traveling Salesman Problems

Approximation Algorithms for Traveling Salesman Problems

Vera Traub, University of Bonn
Jens Vygen, University of Bonn
No date available
Adobe eBook Reader
9781009445429
Adobe eBook Reader

    The Traveling Salesman Problem (TSP) is a central topic in discrete mathematics and theoretical computer science. It has been one of the driving forces in combinatorial optimization. The design and analysis of better and better approximation algorithms for the TSP has proved challenging but very fruitful. This is the first book on approximation algorithms for the TSP, featuring a comprehensive collection of all major results and an overview of the most intriguing open problems. Many of the presented results have been discovered only recently, and some are published here for the first time, including better approximation algorithms for the asymmetric TSP and its path version. This book constitutes and advances the state of the art and makes it accessible to a wider audience. Featuring detailed proofs, over 170 exercises, and 100 color figures, this book is an excellent resource for teaching, self-study, and further research.

    • Serves as a self-contained resource on approximation algorithms for the Traveling Salesman Problem, covering all major results and putting recent developments into context
    • Serves as a starting point for future research with several of the authors' previously unpublished results
    • Guides students and self-learners through the field through pedagogical explanations, detailed proofs, and many exercises and color figures

    Reviews & endorsements

    'This is a fantastic book! Extensive coverage unifies the wide range of attacks on TSP complexity made over the past decade. A great read for experienced researchers and for those looking to join the field.' William Cook, University of Waterloo

    'The wonderful new textbook by Traub and Vygen is a pleasure to read - there have been very successful textbooks on the TSP, and on approximation algorithms, but this is the first to focus on approximation algorithms for the TSP. At first, this might seem like a too repetitive diet, but the richness of the developments of the past decade or so, all elegantly presented here to the last detail, demonstrates the wealth of variety of algorithmic thinking that has produced these advances.' David B. Shmoys, Cornell University

    'Thoroughly Simplified Presentation of the latest approximation results on key variants of the TSP. A gem and a must-read for both novice and experts in the area! Like the 4 C's of a diamond: Clear, Comprehensive, Careful and Captivating.' Michel Goemans, Massachusetts Institute of Technology

    'This book is a very welcome addition to the literature on the fascinating and addicting traveling salesman problem. It gives a consistent and unified treatment of approximation algorithms, starting with a very thorough treatment of the basics and extending through the most recent developments, including work by these two authors. This volume will be valued by researchers and graduate instructors alike.' David P. Williamson, Cornell University

    'This is an amazing book by world-leading experts Vera Traub and Jens Vygen. It comprehensively covers and simplifies recent developments on approximation algorithms for the traveling salesman problem. The clarity and extensive treatment of advanced algorithmic techniques make this book a must-read for anyone interested in advanced algorithmic techniques and approximation algorithms.' Ola Svensson, École Polytechnique Fédérale de Lausanne

    See more reviews

    Product details

    No date available
    Adobe eBook Reader
    9781009445429
    0 pages

    Table 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.