Review of [i]In Pursuit of the Traveling Salesman[/i]

Christopher Thompson (The Florida State University)

In Pursuit of the Traveling Salesman, William J. Cook, 2012, xiii + 228 pp., hardcover, $27.95, ISBN 9780691152707, Princeton University Press, 41 William Street, Princeton, NJ, 08540.

The problem at hand: Given a collection of cities and known pairwise distances, find the shortest route which visits all cities and returns to the starting point. One can easily forget that this seemingly simple yet eloquent task, commonly referred to as the Traveling Salesman Problem (TSP), has eluded the mathematical community for almost a century. In his new book, aptly titled In Pursuit of the Traveling Salesman, William Cook enlists us to join him on a personal journey through all-things past and present regarding this mammoth of a mathematical problem. His book exposes readers to the origins, key developments, and possible future directions of the TSP, complete with colored graphics and historical pictures. References to complexity and the elusive P versus NP problem are also provided.

Portions of this book would be well-suited for classroom use. Although Cook successfully describes a complicated topic in very broad and understandable language, some underlying sections (e.g., comb inequalities, branching) may still be challenging for select audiences to grasp. However, portions of the book could easily be used as supplemental materials to enhance a vast array of high-school level courses. For example, Cook devotes one of his longest chapters to Dantzig’s application of linear programming to the TSP. This would pair nicely with more advanced algebra coursework. Throughout the book there is extensive discussion of history behind the TSP and its applications in biology, art, and other subjects. Teachers looking to incorporate more of the history of mathematics should find this to be a welcome addition to their classroom. There is also much discussion regarding the impact of algorithms and computing on mathematics, a topic which some teachers may wish to include in their curriculum.

One of the strengths of Cook’s take on the TSP is his deliberate linking of multiple branches of mathematics. Developments and progress on the TSP over the decades have utilized numerical analysis, graph theory, algorithm writing, logic, and statistics, among other areas. The connectivity of mathematics is often difficult for students to understand. This book could be used as an example and resource to bridge these types of gaps.

I would highly recommend this book to interested readers and high school mathematics teachers, especially those of upper-level coursework. A great deal of mathematics is covered here and the TSP can easily spark debate and inquiry in the classroom. Who knows, maybe some graduating senior out there who reads this book will eventually claim the $1,000,000 prize from Clay Mathematics Institute, not to mention the Fields Medal that would likely ensue.

See also the MAA Review by Art Gittleman.