In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

First edition
Author	William J. Cook
Language	English
Subject	The traveling salesman problem
Publisher	Princeton University Press
Publication date	2011
ISBN	9781400839599

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation is a book on the travelling salesman problem, by William J. Cook, published in 2011 by the Princeton University Press, with a paperback reprint in 2014. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.^[1]

Topics

The travelling salesman problem asks to find the shortest cyclic tour of a collection of points, in the plane or in more abstract mathematical spaces. Because the problem is NP-hard, algorithms that take polynomial time are unlikely to be guaranteed to find its optimal solution;^[2] on the other hand a brute-force search of all permutations would always solve the problem exactly but would take far too long to be usable for all but the smallest problems.^[3] Threading a middle ground between these too-fast and too-slow running times, and developing a practical system that can find the exact solution of larger instances, raises difficult questions of algorithm engineering,^[4][2] which have sparked the development of "many of the concepts and techniques of combinatorial optimization".^[2]

The introductory chapter of the book explores the limits of calculation on the problem, from 49-point problems solved by hand in the mid-1950s by George Dantzig, D. R. Fulkerson, and Selmer M. Johnson to a problem with 85,900 points solved optimally in 2006 by the Concorde TSP Solver, which Cook helped develop. The next chapters covers the early history of the problem and of related problems, including Leonhard Euler's work on the Seven Bridges of Königsberg, William Rowan Hamilton's Icosian game,^[5] and Julia Robinson first naming the problem in 1949.^[6] Another chapter describes real-world applications of the problem,^[5] ranging "from genome sequencing and designing computer processors to arranging music and hunting for planets".^[7] Reviewer Brian Hayes cites "the most charming revelation" of the book as being the fact that one of those real-world applications has been route planning for actual traveling salesmen in the early 20th century.^[3]

Chapters four through seven, "core of the book", discuss methods for solving the problem, leading from heuristics and metaheuristics, linear programming relaxation, and cutting-plane methods, up to the branch and bound method that combines these techniques and is used by Concorde. The next two chapters also cover technical material, on the performance of computer implementations and on the Computational complexity theory of the problem.^[5][8]

The remaining chapters are more human-centered, covering human and animal problem-solving strategies, and the incorporation of TSP solutions into the artworks of Julian Lethbridge, Robert A. Bosch, and others.^[5][9] A short final summary chapter suggests possible future directions, including the possibility of progress on the P versus NP problem.^[5][10]

Audience

The book is intended for a non-specialist audience, avoids technical detail^[2][4][11] and is written "in an easy to understand style".^[12] It includes many historical asides, examples, applications, and biographical information and photographs of key players in the story, making it accessible to readers without a mathematical background.^[9][11]

Although In Pursuit of the Traveling Salesman is not a textbook, reviewer Christopher Thompson suggests that some of its material on the use of linear programming and on applications of the problem "would be well-suited for classroom use", citing in particular the way it links multiple fields including numerical analysis, graph theory, algorithm design, logic, and statistics.^[13]

Reviewer Stan Wagon writes that "any reader with an interest in combinatorial algorithms will find much of value in this book".^[4] Jan Karel Lenstra and David Shmoys write that "The writing is relaxed and entertaining; the presentation is excellent. We greatly enjoyed reading it."^[2] And reviewer Haris Aziz concludes "The book is highly recommended to any one with a mathematical curiosity and interest in the development of ideas.".^[9]

Related works

More details of Cook's work with Concorde, suitable for more serious researchers on the problem and on related topics, can be found in an earlier book by Cook with David Applegate, Robert E. Bixby and Václav Chvátal, The Traveling Salesman Problem: A Computational Study (2007).^[1][3][9] Other books on the travelling salesman problem, also more technical than In Pursuit of the Traveling Salesman, include The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (by Lawler, Lenstra, Rinnooy Kan, and Shmoys, 1985) and The Traveling Salesman Problem and Its Variations (by Gutin and Punnen, 2006).^[9]

References

Further reading

• Ellenberg, Jordan (March 10, 2012), "The fuzzy path may be shortest (review of In Pursuit of the Traveling Salesman)", The Wall Street Journal
• McLemee, Scott (March 21, 2012), "Algorithm of a salesman (review of In Pursuit of the Traveling Salesman)", Inside Higher Education