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.