William J. Cook

 

On his book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

Cover Interview of February 13, 2012

In a nutshell

You wake up in the morning and find that you need to visit a number of cities or towns before returning in the evening.  What is the shortest possible route to bring you to each of the locations and safely home again?

Sounds simple enough, but it is in fact a long-standing open question in mathematics—known as the traveling salesman problem, or TSP for short.

As an existential problem, any particular example of salesman routing poses no real challenge.  The task comes down to determining the order in which we should visit the locations on our list.  To find the best route we simply check each possible ordering and record the shortest.

So the solution for the salesman is out there, but can we actually find it?

A quick counting argument will convince you that when faced with fifty locations or so, all of the world’s computers together could not possibly check each possible ordering.  The question is whether we can quickly sift through this impossibly large number of routes and pull out the shortest.  Developing such an efficient solution method for the TSP is the focal point of an intense study by the research community into the nature of complexity.

In Pursuit of the Traveling Salesman traces the history of how mathematicians have slowly come to grips with the salesman problem—and how its study has led to a better understanding of the world around us.  The book is aimed at a general audience, adopting the TSP to give a tour of modern applied mathematics and some of the important questions we face in the information age.