In Pursuit of the Traveling Salesman

From HandWiki
In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
In Pursuit of the Traveling Salesman.jpg
First edition
AuthorWilliam J. Cook
LanguageEnglish
SubjectThe traveling salesman problem
PublisherPrinceton University Press
Publication date
2011
ISBNISBN: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

  1. ↑ 1.0 1.1 Gittleman, Art (February 2012), "Review of In Pursuit of the Traveling Salesman", MAA Reviews (Mathematical Association of America), https://www.maa.org/press/maa-reviews/in-pursuit-of-the-traveling-salesman-mathematics-at-the-limits-of-computation 
  2. ↑ 2.0 2.1 2.2 2.3 2.4 "Review of In Pursuit of the Traveling Salesman", Notices of the American Mathematical Society 63 (6): 635–638, 2016, doi:10.1090/noti1397 
  3. ↑ 3.0 3.1 3.2 "Mathematical road trips (review of In Pursuit of the Traveling Salesman)", American Scientist 100 (3): 252–254, May–June 2012 
  4. ↑ 4.0 4.1 4.2 "Review of In Pursuit of the Traveling Salesman", American Mathematical Monthly 119 (9): 808–811, 2012, doi:10.4169/amer.math.monthly.119.09.808 
  5. ↑ 5.0 5.1 5.2 5.3 5.4 Werner, Frank (2012), "Review of In Pursuit of the Traveling Salesman", Mathematical Reviews 
  6. ↑ Schuessler, Jennifer (March 15, 2012), "Willy Loman, Where Are You? (Review of In Pursuit of the Traveling Salesman)", The New York Times, https://archive.nytimes.com/query.nytimes.com/gst/fullpage-9E0DE0D9113BF936A25750C0A9649D8B63.html 
  7. ↑ Benker, Hans, "Review of In Pursuit of the Traveling Salesman", zbMATH 
  8. ↑ Baldacci, Roberto (July–August 2013), "Review of In Pursuit of the Traveling Salesman", Interfaces 43 (4): 391 
  9. ↑ 9.0 9.1 9.2 9.3 9.4 Aziz, Haris (August 2012), "Review of In Pursuit of the Traveling Salesman", ACM SIGACT News 43 (3): 51, doi:10.1145/2421096.2421108 
  10. ↑ McGonigal, Francis (January 2012), "Review of In Pursuit of the Traveling Salesman", IMA Book Reviews (Institute of Mathematics and its Applications), https://ima.org.uk/311/in-pursuit-of-the-traveling-salesman-mathematics-at-the-limits-of-computation/ 
  11. ↑ 11.0 11.1 Tirado Domínguez, Gregorio (November 2012), "Review of In Pursuit of the Traveling Salesman", EMS Reviews (European Mathematical Society), https://euro-math-soc.eu/review/pursuit-traveling-salesman 
  12. ↑ Schaefer, Robert (January 2012), "Review of In Pursuit of the Traveling Salesman", New York Journal of Books, https://www.nyjournalofbooks.com/book-review/pursuit-traveling-salesman-mathematics-limit-computation 
  13. ↑ Thompson, Christopher (February 2012), "Review of In Pursuit of the Traveling Salesman", Convergence (Mathematical Association of America), doi:10.4169/loci003821 

Further reading



Retrieved from "https://handwiki.org/wiki/index.php?title=In_Pursuit_of_the_Traveling_Salesman&oldid=2627828"