Review of "In Pursuit of the Traveling Salesman"
Review of
In Pursuit of the Traveling Salesman
William J. Cook
2012
245 pages, Hardcover
“The traveling-salesman problem is one of the great unsolved problems in
mathematics, capturing notions of complexity that are at the core of the
information age.”— W. J. Cook [4].
Introduction
The traveling salesman problem (TSP) is one of the most fundamental and ubiquitous computational problems. W. J. Cook has written a book which tries to explain the intellectual challenge of coming up with an efficient way to solve TSP. This book tells the tale of how TSP has captured the minds of various mathematicians and computer scientists in history and how the quest to solve TSP has led to many breakthroughs in the field of combinatorial optimization. It appears to be the layman’s version of [3] which is a comprehensive book covering technical aspects in much more detail.
Summary
The book consists of twelve chapters.
Chapter 1 (“Challenges ”) introduces the challenge of the TSP and explains the combinatorial difficulty of solving the problem without having to enumerate and compare an exponential number of tours.
In Chapter 2 (“Origins of the Problem ”), the author explores the origin of the problem. He
describes how even before mathematicians examined the problem formally, salesmen, lawyers, and preachers encountered the TSP in their travels. This is followed by research on how TSP was formalized as a scientific problem.
In Chapter 3 (“The Salesman in Action ”), the modern-day applications of the TSP are outlined which includes mapping genomes, industrial machines, organizing data, scheduling jobs etc.
Chapter 4 (“Searching for a Tour ”) initiates the formal study of the TSP and describes the
fundamental approaches to searching for optimal tours.
In Chapter 5 (“Linear Programming ”), linear programming is introduced and it is explained
how LP relaxations are useful in finding good tours efficiently.
In Chapter 6 (“Cutting Planes ”) the cutting-plane method is discussed in detail.
Chapter 7 (“Branching ”) then explores branching in the use of combinatorial optimization.
Chapter 8 titled “Big Computing” covers the algorithmic engineering aspect of the TSP.
Various practical milestones are mentioned and historical world records in solving big TSP problems are highlighted.
Chapter 9 titled “Complexity” consists of an exposition on formal computational complexity
including Turing machines; the desirability of polynomial-time algorithms; polynomial-time reductions; NP-complete problems etc.
Chapter 10 and 11 discuss miscellaneous aspects. In Chapter 10 (“The Human Touch”), the
use of the human mind is compared to the computer. The problem solving strategies of animals are also covered. Chapter 11 (“Aesthetics ”) examined the aesthetic and artistic aspects of the TSP and especially how TSP has been adopted in several works of modern art.
The book concludes with Chapter 12 with anticipation about the next episodes in the unfolding story of the TSP.
The back matter consists of notes, bibliography, and an index.
Opinion
TSP is a fundamental problem in combinatorial optimization and theoretical computer science and a number of books have been written which are dedicated solely to TSP [see for example, 3, 6, 5]. This book is unique in the sense that it tries to convey interesting technical ideas to the general public. Passages from the book could easily be used to as accessible introductions to topics in combinatorial optimization. For example, a part of Chapter 5 is a mini-tutorial on linear programming and Chapter 9 presents a gentle introduction to computational complexity.
Not only does Cook make an excellent effort to convey elegant ideas from theoretical computer science to the public but does so in an upbeat and engaging manner. In this effort, Cook helps his cause by conveying the human side of the research story. As in sports and arts, the human aspects of the performance adds an extra layer of public interest. Cook manages to bring his passion for mathematical research to the fore. There are mini-biographies or at least mention of most of the actors involved in story of the TSP. The list includes but is not restricted to Euler, William, Hamilton, Menger, Hassler Whitney, Jack Edmonds, Richard Karp, Stephen Cook, Dantzig, Nicos Christofides, Shen Lin, Brian Kernighan, Robert Tarjan, and David Johnson. In this sense, the
book is similar in flavor to popular science books by Simon Singh which discuss interesting scientific problems or questions and tell the story of scientific problems which spans decades, continents, and a number of characters and ideas [see for example, 8]. Along with the text, one also notices the photographs of various mathematicians and computer scientists associated with the story of TSP.
Although the book contains many ideas, it is suitable for leisurely reading. Each chapter starts with a well-chosen quotation and focusses on one aspect of TSP. The text in “In Pursuit of the Traveling Salesman” is accompanied by figures and pictures. One also encounters humor. For example when the author discusses Stephen Cook, he quips “No relation to me, although I have enjoyed a number of free dinners due to mistaken identity.” There is a companion website which further captures the excitement around the TSP [2]. It is evident that a lot of research has gone into retracing the history of TSP and identifying crucial breakthroughs. It would have been appealing had the author made a timeline of the various milestones in the challenge of TSP just as Plummer [7] did for matching theory. I feel that the book serves well for the outreach and dissemination for theoretical computer science. Incidentally a movie titled “Travelling Salesman” but independent from the book (to the best of my knowledge) is also planned for 2012 which will further help the
cause [1].
The book is highly recommended to any one with a mathematical curiosity and interest in the
development of ideas.
References
[1] http://www.travellingsalesmanmovie.com/, April 2012.
[2] http://www.tsp.gatech.edu/, April 2012.
[3] D. L. Applegate, R. E. Bixby, and W. J. Cook. The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics. Princeton University Press, 2007.
[4] W. J. Cook. The problem of the traveling politician. NYT Blogs, 2011.
[5] G. Gutin and A. P. Punnen. The Traveling Salesman Problem and Its Variations, Springer, 2006.
[6] E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys. The Traveling Salesman
Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons, 1985.
[7] M. D. Plummer. Matching theory - a sampler: from d´enes k¨onig to the present. Discrete
Mathematics, 100:177–219, 1992.
[8] S. Singh. Fermat’s Last Theorem: The story of a ridd le that confounded the world’s greatest minds for 358 years. Fourth Estate, 2002.
Comments