In Pursuit of the Traveling Salesman by William Cook
October 2012
Recently read an interesting book on the traveling salesman problem. I initially expected the book to be aimed at a more general audience and have the depth of a typical popular science book, but the topics were much more technical. The book is well-written and an entertaining read. Assuming a motivated instructor who could explain the more technical details missing from the book, it could serve as a textbook for an advanced undergraduate course. I think it would be a course I would have enjoyed as an undergraduate and one I would be excited to try and teach today.
The first three chapters discuss the history of the problem and its myriad applications. Chapter 4 presents a broad overview of the general approaches to solving the TSP. Chapter 5—with the introduction of linear programming—is when things really become interesting. He also discusses the simplex method and briefly talks about integer programming.
These are concepts that I wasn’t introduced to until graduate school in Computer Science. He does a good job of illustrating the ideas and demonstrates the method with a simple example. However, from this point, I’m not sure how much a reader will get from the book without a strong mathematical or computational foundation. He also introduces the reader to operations research and points to an interesting operations research blog (One particularly interesting post examines which country won the Olympics by setting up possible weights on the gold, silver, and bronze medal counts as a linear programming problem. The “winner” is the country that owns the majority of the solution space.).
He ends with a discussion of human and animal solutions to the TSP and a review of artists who are motivated by the TSP. The introduction of the reader to the idea of not just algorithmic solutions to problems, but “good” solutions is a strong point of the book. The description of Turing Machines and P vs. NP is as good as any I have seen outside of traditional textbooks.
Readers are left with several open problems that could serve as a starting point for budding TSP researchers:
- Is the Euclidean TSP in NP?
- Is there an algorithm provably faster than the \(n^2 2^n\) result of Held-Karp?
- Is there a polynomial time algorithm guaranteed to produce a tour no more than 1.5 times the optimal?
In the end, the book is not a comprehensive study of the TSP, but an introduction and high-level overview that does touch on specific theoretical and computational issues. I was intrigued by the discussions in the book and I will be seeking out more detailed information about the ideas discussed in the book. My guess is that was the true goal of the author.