In pursuit of the traveling salesman : mathematics at the limits of computation
 Author/Creator
 Cook, William, 1957
 Language
 English.
 Imprint
 Princeton, N.J. : Princeton University Press, c2012.
 Physical description
 xiii, 228 p. : ill. (chiefly col.), col. maps ; 24 cm.
Access
Available online

Stacks

Unknown
QA164 .C69 2012

Unknown
QA164 .C69 2012
More options
Contents/Summary
 Bibliography
 Includes bibliographical references (p. [223]224) and index.
 Contents

 1. Challenges
 Tour of the United States
 An impossible task?
 One problem at a time
 Road map of the book
 2. Origins of the problem
 Before the mathematicians
 Euler and Hamilton
 Vienna to Harvard to Princeton
 And on to the RAND Corporation
 A statistical view
 3. The salesman in action
 Road trips
 Mapping genomes
 Aiming telescopes, xrays, and lasers
 Guiding industrial machines
 Organizing data
 Tests for microprocessors
 Scheduling jobs
 And more
 4. Searching for a tour
 The 48states problem
 Growing trees and tours
 Alterations while you wait
 Borrowing from physics and biology
 The DIMACS challenge
 Tour champions
 5. Linear programming
 Generalpurpose model
 The simplex algorithm
 Two for the price of one: LP duality
 The degree LP relaxation of the TSP
 Eliminating subtours
 A perfect relaxation
 Integer programming
 Operations research
 6. Cutting planes
 The cuttingplane method
 A catalog of TSP inequalities
 The separation problem
 Edmonds's glimpse of heaven
 Cutting planes for integer programming
 7. Branching
 Breaking up
 The search party
 Branchandbound for integer programming
 8. Big computing
 World records
 The TSP on a grand scale
 9. Complexity
 A model of computation
 The campaign of Jack Edmonds
 Cook's theorem and Karp's list
 State of the TSP
 Do we need computers?
 10. The human touch
 Humans versus computers
 Tourfinding strategies
 The TSP in neuroscience
 Animals solving the TSP
 Aesthetics
 Julian Lethbridge
 Jordan curves
 Continuous lines
 Art and mathematics
 Pushing the limits.
 Summary
 "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 mathematicsand 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 stateoftheart 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 traveling 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 traveling salesman problem isliterallya $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"Provided by publisher.
 "In Pursuit of the Traveling Salesman covers the history, applications, theory, and computation of the traveling salesman problem right up to stateoftheart solution machinery"Provided by publisher.
Subjects
Bibliographic information
 Publication date
 2012
 Responsibility
 William J. Cook.
 ISBN
 9780691152707
 0691152705