- Home
- In Pursuit of the Traveling Salesman

# In Pursuit of the Traveling Salesman

Mathematics at the Limits of Computation

**William J. Cook **

- Paperback2014Paperback16.9514.95ISBN9780691163529248 pp.6 x 9 1/4113 color illus. 19 halftones. 19 line illus. 2 tables.Live

- E-bookISBN9781400839599

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.

*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).

## Reviews

**--Pradeep Mutalik, Wordplay blog at**

*New York Times**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**In Pursuit of the Traveling Salesman*is a thoroughly entertaining nerd-fest for the science minded reader."

**--Robert Schaefer,**

*New York Journal of Books**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**

**--Michael Trick's Operations Research Blog**

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

*Choice***--Robert Terpstra,**

*Business Today Egypt***--Gregorio Tirado Domínguez,**

*European Mathematical Society***--Haris Aziz,**

*ACM SIGACT News***--Gabor Pataki,**

*INFORMS Journal on Computing***--S. Leigh Nataro,**

*Mathematics Teacher***--Roberto Baldacci,**

*Interfaces***--Francis McGonigal,**

*Mathematics Today*## Endorsements

*In Pursuit of the Traveling Salesman*deserves to become an instant classic."

**--Ian Stewart, author of**

*Professor Stewart's Hoard of Mathematical Treasures***--Stan Wagon, Macalester College, author of**

*Mathematica in Action***--Mitchel T. Keller, London School of Economics and Political Science**

## Table of Contents

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

## Other Books Written by this Author(s)

- William J. Cook

## Subject Areas

## Series

## Shopping Cart Options

### For eBooks

**Many of our ebooks are available throughlibrary electronic resources including these platforms:**

Our eBook editions are available from these online vendors:

### For hardcover/paperback orders in **United States, Canada, Latin America, Asia, and Australia**

### For hardcover/paperback orders in **Europe, Africa, the Middle East, India, and Pakistan**

**Prices subject to change without notice**

### Princeton University Press

41 William Street

Princeton, New Jersey 08540 USA

webmaster@press.princeton.edu

609-258-4900

**USD Orders online, e-mail: IPSJacksonOrders@ingramcontent.com. For GBP orders online, e-mail: customer@wiley.com.
For more detailed ordering information, see: http://press.princeton.edu/ordering.html.**