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

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

[T]he Holocaust transformed our whole way of thinking about war and heroism. War is no longer a proving ground for heroism in the same way it used to be. Instead, war now is something that we must avoid at all costs—because genocides often take place under the cover of war. We are no longer all potential soldiers (though we are that too), but we are all potential victims of the traumas war creates. This, at least, is one important development in the way Western populations envision war, even if it does not always predominate in the thinking of our political leaders.

The dominant premise in evolution and economics is that a person is being loyal to natural law if he or she attends to self’s interest and welfare before being concerned with the needs and demands of family or community. The public does not realize that this statement is not an established scientific principle but an ethical preference. Nonetheless, this belief has created a moral confusion among North Americans and Europeans because the evolution of our species was accompanied by the disposition to worry about kin and the collectives to which one belongs.

## 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.