cook_william

William

J.

Cook

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

Cover Interview of

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.

February 13, 2012

The wide angle

A home of TSP studies is the field of applied mathematics known as operations research. The focus of the field is the creation of methods to improve decision making, in particular for efficient use of scarce resources.

The TSP arises in many operations-research settings, some wildly distinct from salesmen driving through the countryside. The problem is used in genetic sequencing, package delivery, hunting for planets, and designing computer processors. The book covers these and many other applications, describing how even approximate solutions to the salesman problem improve both industry and science.

In operations research, a challenge is to solve large instances of the TSP, using any means available. This is a take-no-prisoners approach to the problem, and it has led to almost unbelievable progress in TSP computation. I describe in the book the successful tools that have been developed, and give an account of the computational attacks themselves, including the calculation of a nearly shortest tour for the World TSP challenge, covering all 1,904,711 cities around the globe.

A different view of the problem is taken in the field of theoretical computer science, where the focus is on the design of algorithms that include performance guarantees. By an algorithm we mean a step-by-step recipe to construct a tour, capable of handling any instance of the TSP we may throw at it. The guarantees are in terms of the quality of the tour that will be produced and the running time of a proposed algorithm.

The (literally) million-dollar question is whether or not there exists an algorithm that can efficiently solve every example of the TSP. Just solving for every city in the world or even every star in the universe is not sufficient. In this context we must be prepared to solve any example of the problem, including those that have yet to be imagined.

This brings the TSP into the realm of one of the greatest unsolved challenges in mathematics, known as the “P versus NP” question. Finding an efficient algorithm for the TSP will settle the question and earn $1,000,000 from the Clay Mathematics Institute.

The TSP is one of a great variety of nice problems—ones for which it is easy to verify that an answer is correct.

In the case of the TSP, suppose we need to complete our trip within eight hours: if someone, or some algorithm, presents us with a tour, we can check easily that the total driving time comes in under our eight-hour target.

Using deep theory developed in the 1960s, an efficient algorithm for the TSP would provide efficient methods for solving all nice problems! This may well be impossible—but no one knows for sure.

The Clay Institute will also pay $1,000,000 for a proof of impossibility; settling the matter one way or the other will earn the big money.

If you are short of cash, the book gives the details you need to get started on P versus NP.

February 13, 2012

A close-up

In the hands of your browsing reader, I’d like the book to fall open to a pair of pages displaying two paintings by Julian Lethbridge, Traveling Salesman and Traveling Salesman 4. These are not pieces of mathematics, but they capture well the beauty of the salesman problem that attracts so many mathematicians to its study.

A traveler concerned about mileage will not cross her own path during a tour. Thus a shortest tour can be drawn as a line that loops around but never crosses itself. Such a line, known as a Jordan curve, divides space into two regions, an inside and an outside. Think of a fence running around the boundary of a park or think of the coastline of an island.

The first of Lethbridge’s paintings shows vividly the division of space created by a good solution to the salesman problem. Lethbridge uses colors and textures to highlight the interior and exterior, separated by a rendering of the tour itself. The division of space feels natural, suggesting that short tours are, in a sense, organic objects.

The second painting displays the same tour as the first, but highlights the complexity of discovering the partition of space inherent in the locations of the points to be visited. Lethbridge uses multiple colored strokes emanating from each turn of the salesman tour. Following the strokes from point to point, one quickly gets lost in the myriad of alternative paths.

February 13, 2012

Lastly

In Pursuit of the Traveling Salesman aims to spread the word that mathematics is alive and well.

In the TSP we have a simply stated problem that nonetheless gets to the heart of modern complexity issues and has important applications in numerous settings. The fact that future progress, and perhaps a million-dollar prize, may lie at the tip of the reader’s pencil can hopefully serve to capture the attention and imagination of young and old alike.

If I can attract a few people to join the next generation of applied mathematicians, then the book will have been a success.

February 13, 2012
William J. Cook In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation Princeton University Press 272 pages, 6 x 9 inches ISBN 978 0 691 15270 7
cook_w_pursuit_salesman
cook_william

William Cook is the Chandler Family Chair and Professor at Georgia Tech. He is a member of the National Academy of Engineering and a fellow of the Society for Industrial and Applied Mathematics and of the Institute for Operations Research and Management Sciences.

Cover Interview of
February 13, 2012