Synopses & Reviews
"A gripping insider's account of one of the great mathematical problems. This book shows how deep mathematical insights can arise from apparently simple questions, and how the results can be applied to that most human of objectives: to achieve a desired outcome in the best possible way.
In Pursuit of the Traveling Salesman deserves to become an instant classic."
--Ian Stewart, author of Professor Stewart's Hoard of Mathematical Treasures"I found this to be a wonderful book on many levels. The writing is informal but precise, and a lot of ground is covered. Cook ties together so many diverse topics and includes informative discussions about the history. I now know a lot more about every aspect of the traveling salesman problem."--Stan Wagon, Macalester College, author of Mathematica in Action
"Cook makes a compelling case for the importance of the traveling salesman problem, revealing that while many brilliant minds have worked on the problem, the next key insight could really come from anyone. Because of his centrality to the research, he writes with a depth of knowledge and experience that few--if any--can surpass. I know of no other book like this."--Mitchel T. Keller, London School of Economics and Political Science
Review
"Fascinating . . . describes the history, personalities, challenges, applications and techniques used to find solutions of the famous 'Traveling Salesman Problem' and related problems."--Pradeep Mutalik, Wordplay blog at New York Times
Review
"The Traveling Salesman Problem, or TSP, might seem to be of purely recreational interest . . . but in fact, as William J. Cook's In Pursuit of the Traveling Salesman ably shows, the problem remains a topic of hot interest. . . . [This book is] an excellent place for an interested amateur to get the gist of these big ideas in a down-to-earth discussion. . . . Mr. Cook's affable style means that you're never too far from an enjoyable historical anecdote or an offbeat application of a problem that has interested some of the best minds in applied math for most of a century and that shows no signs of getting stale."--Jordan Ellenberg, Wall Street Journal
Review
"The author, William Cook, writes in an easy to understand style and explores the various algorithms and branches of mathematics used to solve TSP, including the branch of mathematics known as linear programming, which is known to most of us through grade school algebra and word problems. . . . In Pursuit of the Traveling Salesman is a thoroughly entertaining nerd-fest for the science minded reader."--Robert Schaefer, New York Journal of Books
Review
"Along with a heady dose of algorithms, Cook also offers a diverting survey of the lore and history of the TSP. . . . The new volume addresses a wider audience [than The Traveling Salesman Problem: A Computational Study], with more pictures and fewer equations, explaining how things are done rather than how to do them, but it covers all the same territory as the larger book. The path through that territory seems reasonably close to optimal."--Brian Hayes, American Scientist
Review
"In Pursuit of the Traveling Salesman is a first-hand and a first-class introduction into the evolution of TSP, with chapters devoted to related mathematics and algorithmic topics. TSP is really at the heart of much of the research and development of modern computer science, so the author leads the reader through the past and emerging landscape of relevant research up to the very end of the mapped territory. Reading the book looks like an exciting adventure, with the itinerary mapped for the reader by a master story-teller whose work squarely places him in the forefront of the TSP research."--Alexander Bogomolny, Cut the Knot Insights blog
Review
"Bill takes his readers down a beautiful path covering the history, applications, and algorithms associated with the TSP. It is a fascinating story, and one that shows a researcher who truly loves his research area. . . . Through this book, you'll learn all about the Traveling Salesman Problem and, more broadly, about the different research directions in combinatorial optimization."--Michael Trick's Operations Research Blog
Review
"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. . . . 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."--Christopher Thompson, Loci: Convergence
Review
"In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, does a wonderful job presenting the history and significance of the TSP and an overview of cutting-edge research. It's a beautiful, visually rich book, full of color photographs and diagrams that enliven both the narrative and mathematical presentation. And it includes a wealth of information."--Math Less Traveled
Review
"This book introduces the TSP, its applications, and computational methods for its solution to a general audience."--Choice
Review
"Cook is spot-on in his delivery of what could be considered by most as an arcane mathematical problem to be solved by only those in the engineering world but like Hawking, peaks interest in a field in which lowly MIT professors could only dream. . . . His witty commentary complements his own casual insertion into the mathematical world and drive to solve the greatest of mathematics' problems. This book is proof that good science writing and mathematics add up."--Robert Terpstra, Business Today Egypt
Review
"The technical details are described with precision, but the inherent mathematical concepts are explained in an informal way so that readers without a deep mathematical background can also follow the story. . . . The book is full of examples, real applications and historical anecdotes, making it really enjoyable to read."--Gregorio Tirado Domínguez, European Mathematical Society
Review
"The book is highly recommended to any one with a mathematical curiosity and interest in the development of ideas."--Haris Aziz, ACM SIGACT News
Review
"[T]here is sufficient mathematical detail to provide a good start to readers interested in a more technical treatment. The style is congenial, breezy, and entertaining; many anecdotes and pop culture references are included. Even seasoned researchers will find the book a truly enjoyable read, and it can serve as an ideal basis for a college level freshman seminar."--Gabor Pataki, INFORMS Journal on Computing
Review
"The author has a solid understanding of the material and tries to present it in an accessible and sometimes entertaining way. . . . I recommend it to anyone interested in gaining a deeper understanding of the TSP and modern developments in solving TSP-like problems."--S. Leigh Nataro, Mathematics Teacher
Review
"[T]his book presents the history and significance of the TSP, and provides an overview of this cutting-edge research in a wonderful way. I recommend it to anybody who is interested in a down-to-earth discussion that provides the most current information on the TSP."--Roberto Baldacci, Interfaces
Review
"This book covers all facets of the TSP and ventures into some very deep theory of complexity and computability. It is written for the general mathematician or scientist but would also be useful to the OR specialist. Overall it is entertaining, richly illustrated and well-referenced. It tells us much about general problem solving as well as the TSP."--Francis McGonigal, Mathematics Today
Synopsis
What is the shortest possible route for a traveling salesman seeking to visit each city on a list exactly once and return to his city of origin? It sounds simple enough, yet the traveling salesman problem is one of the most intensely studied puzzles in applied mathematics--and it has defied solution to this day. In this book, William Cook takes readers on a mathematical excursion, picking up the salesman's trail in the 1800s when Irish mathematician W. R. Hamilton first defined the problem, and venturing to the furthest limits of today's state-of-the-art attempts to solve it. He also explores its many important applications, from genome sequencing and designing computer processors to arranging music and hunting for planets.
In Pursuit of the Traveling Salesman travels to the very threshold of our understanding about the nature of complexity, and challenges you yourself to discover the solution to this captivating mathematical problem.
About the Author
William J. Cook is professor of combinatorics and optimization at the University of Waterloo. He is the coauthor of The Traveling Salesman Problem: A Computational Study (Princeton).
Table of Contents
Preface xi
Chapter 1: Challenges 1
Tour of the United States 2
An Impossible Task? 6
One Problem at a Time 10
Road Map of the Book 16
Chapter 2: Origins of the Problem 19
Before the Mathematicians 19
Euler and Hamilton 27
Vienna to Harvard to Princeton 35
And on to the RAND Corporation 38
A Statistical View 39
Chapter 3: The Salesman in Action 44
Road Trips 44
Mapping Genomes 49
Aiming Telescopes, X-rays, and Lasers 51
Guiding Industrial Machines 53
Organizing Data 56
Tests for Microprocessors 59
Scheduling Jobs 60
And More 60
Chapter 4: Searching for a Tour 62
The 48-States Problem 62
Growing Trees and Tours 65
AlterationsWhile You Wait 75
Borrowing from Physics and Biology 84
The DIMACS Challenge 91
Tour Champions 92
Chapter 5: Linear Programming 94
General-Purpose Model 94
The Simplex Algorithm 99
Two for the Price of One: LP Duality 105
The Degree LP Relaxation of the TSP 108
Eliminating Subtours 113
A Perfect Relaxation 118
Integer Programming 122
Operations Research 125
Chapter 6: Cutting Planes 127
The Cutting-Plane Method 127
A Catalog of TSP Inequalities 131
The Separation Problem 137
Edmonds's Glimpse of Heaven 142
Cutting Planes for Integer Programming 144
Chapter 7: Branching 146
Breaking Up 146
The Search Party 148
Branch-and-bound for Integer Programming 151
Chapter 8: Big Computing 153
World Records 153
The TSP on a Grand Scale 163
Chapter 9: Complexity 168
A Model of Computation 169
The Campaign of Jack Edmonds 171
Cook's Theorem and Karp's List 174
State of the TSP 178
Do We Need Computers? 184
Chapter 10: The Human Touch 191
Humans versus Computers 191
Tour-finding Strategies 192
The TSP in Neuroscience 196
Animals Solving the TSP 197
Chapter 11: Aesthetics 199
Julian Lethbridge 199
Jordan Curves 201
Continuous Lines 205
Art and Mathematics 207
Chapter 12: Pushing the Limits 211
Notes 213
Bibliography 223
Index 225