Approximation Algorithms for Traveling Salesman Problems

‘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

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.