William J. Cook

 

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

Cover Interview of 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.