In Pursuit of the Traveling Salesman
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
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
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
References
- ^ a b Gittleman, Art (February 2012), "Review of In Pursuit of the Traveling Salesman", MAA Reviews, Mathematical Association of America
- ^ MR 3495222
- ^ JSTOR 23223051
- ^ MR 3013985
- ^ MR 2866515
- ^ Schuessler, Jennifer (March 15, 2012), "Willy Loman, Where Are You? (Review of In Pursuit of the Traveling Salesman)", The New York Times
- Zbl 1236.00007
- JSTOR 23481217
- ^
- ^ McGonigal, Francis (January 2012), "Review of In Pursuit of the Traveling Salesman", IMA Book Reviews, Institute of Mathematics and its Applications
- ^ a b Tirado Domínguez, Gregorio (November 2012), "Review of In Pursuit of the Traveling Salesman", EMS Reviews, European Mathematical Society
- ^ Schaefer, Robert (January 2012), "Review of In Pursuit of the Traveling Salesman", New York Journal of Books
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