In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

The traveling salesman problem is a popular computation problem that has evaded a simple solution. The goal is to travel from one point through a number of different points just once and eventually return to the starting point. There are practical applications in route planning as well as many other areas. However, the solution has evaded a simple solution. The brute force solution grows exponentially as more points are added. Some heuristics can be used to help get a "good" solution and then iterate on it until it becomes optimal.

In Pursuit of the Traveling Salesman attempts to be accessible, with a great deal of the text focussed on the history and the people involved. However, it also delves deep into the math. I found myself lost with some of the numbers and optimal solutions. Why are these numbers getting bigger? How are we sure this is the optimal solution. These may have been explained earlier, but I had lost it.

Luckily, the focus is primarily on the people. Even if you get lost with the math, you can follow along with the people. Of key importance is the concept of Linear Programming introduced by George Dantzig. (He had a somewhat auspicious start, solving some "unsolved" statistics problems that he thought were homework.) I got a general idea about how linear programming worked from the text, but it does not really attempt to be a tutorial.

The end of the book presents a number of interesting uses and attempts to solve the traveling salesman problem. Some researchers have used animals grabbing food. Others have attempted to use DNA. People can do a pretty good job with a small set. However, with big sets, they bog down. Some really complex problems involve attempting to trace paths on famous paintings.

The big mystery is still P=NP. Is the salesman problem a difficult problem without an easy solution? Or is there a way that anything can be solved in a reasonable time? There is still a million dollar reward out there, so we may find out.