In Pursuit of the Traveling Salesman

What is the shortest possible route for a travelling salesman seeking to visit each city on a list exactly once and return to his city of origin? It sounds simple enough, yet the travelling 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. Cook examines the origins and history of the salesman problem and explores its many important applications, from genome sequencing and designing computer processors to arranging music and hunting for planets. He looks at how computers stack up against the travelling salesman problem on a grand scale, and discusses how humans, unaided by computers, go about trying to solve the puzzle. Cook traces the salesman problem to the realms of neuroscience, psychology, and art, and he also challenges readers to tackle the problem themselves. The travelling salesman problem is - literally - a $1 million question. That's the prize the Clay Mathematics Institute is offering to anyone who can solve the problem or prove that it can't be done. "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.

ISBN 0691152705   Pages 272 ISBN13 9780691152707 (What's this?)   Weight (grammes) 571 Publisher Princeton University Press   Published in New Jersey Imprint Princeton University Press   Height (mm) 229 Format Hardback   Width (mm) 152 Publication date 27 Dec 2011   Spine width (mm) 21 DEWEY 511.5   Academic level General, Tertiary education DEWEY edition DC23

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

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 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 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 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 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 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 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 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

 Be the first to write a customer review