In Pursuit of the Traveling Salesman

Author(s): 
William J. Cook
Publisher: 
Princeton
Year: 
2012
ISBN: 
978-0-691-15270-7
Price (tentative): 
27.95 dollars
Short description: 

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.

MSC main category: 
90 Operations research, mathematical programming
MSC category: 
90B06
Other MSC categories: 
05C45
Review: 

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

Comments

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Copy the characters (respecting upper/lower case) from the image.