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.

[M]odern art still commonly refers to a rather narrow range of meaning and scope. It basically focuses on developments in Paris (Impressionism etc.) in the nineteenth century, and to selected Euro-American movements in the twentieth century (Cubism, Abstract Expressionism etc). But if we understand modernity as a socially transformative condition that was in force across much of the world from the nineteenth century on, how are we to understand artistic practices that were associated with these momentous changes?

The two world wars of the twentieth century were a product of the dislocations brought about of modernization in an environment where great power competition and the drive for hegemony were conducted primarily by violent means. Now that this era has passed in Europe and is receding in much of the Pacific rim, and hegemony achieved by force is no longer considered a legitimate ambition, the security requirements and fears of great powers should decline.

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