In Pursuit of the Traveling Salesman

There are many mathematical problems whose formulation is so easy that it can be understood by anybody, even without any mathematical background, but, however, are extremely difficult to solve. The book under review is focused on one of these problems, called the Traveling Salesman Problem (TSP). It consists on finding the shortest possible route for a traveling salesman to visit each of his customers exactly once and go back home. The formulation is simple, but after several decades of intense research, it still remains unsolved.

The book begins with an amusing description of the problem, focusing on its undeniable practical origins and presenting innumerable real applications. The complexity issues related to solving the TSP are also introduced, and then a historical tour through the main approaches to the problem is performed, revising the most important mathematical techniques used and highlighting the research lines joining different solution methods. The technical details are described with precision, but the inherent mathematical concepts are explained in an informal way so that readers without a deep mathematical background can also follow the story.

The book is full of examples, real applications and historical anecdotes, making it really enjoyable to read. At the end there is a section devoted to the relation of the TSP with several works of art, showing how the complexity of the problem is so attractive to researchers and artists and highlighting the beauty of its geometry and mathematical properties. The book finishes with a discussion on the future research on the problem, commenting on several possible lines and emphasizing that there is still a lot to be done.

Reviewer: 
Gregorio Tirado Domínguez
Affiliation: 
Universidad Complutense de Madrid
Book details

This book describes the history around one of the most important mathematical problems approached during the last century: the traveling salesman problem. It goes from the origins of the problem to some of the most sophisticated approaches, illustrating this trip with examples, real applications and historical anecdotes.

Author:  Publisher: 
Published: 
2012
ISBN: 
978-0-691-15270-7
Price: 
27.95 dollars
Categorisation