William J. Cook's "In Pursuit of the Traveling Salesman"

William Cook is a professor in the School of Industrial and Systems Engineering at Georgia Tech and a member of the National Academy of Engineering.

He applied the “Page 99 Test” to his new book, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, and reported the following:

Any mathematician will tell you that coincidences are not as rare as we might think. So maybe you should not be surprised to learn that this is the second 99 test I've faced this week. The first is playing out on the roads of Iowa.

In mid-December, together with two Princeton professors, I computed the shortest route to visit all 99 county seats in the state. This was the basis of an op-ed piece that appeared in the New York Times political pages. The tie-in was the mad scrambles taken by presidential hopefuls in front of the January caucuses.

Des Moines columnist Kyle Munson is now putting our optimal route to the test. Munson is driving his Ford Focus from county to county in an attempt to complete the state tour, known as a Full Grassley, in a single week.

Finding the shortest route to visit a list of cities, such as the 99 in Iowa, is known in mathematical circles as the traveling salesman problem. It is not only known, it is despised. Or loved, depending on your point of view. The emotions come from the fact that, despite its simple description, no one knows a method that can solve quickly every example of the problem. There is even a $1,000,000 prize offered to the first person to succeed, or to prove that it is impossible.

For now, if you want to get a shortest route for a specific example of the traveling salesman problem, you need to employ a tool called linear programming. This is the topic of the paragraph in the middle of page 99.

The scope of the use of linear programming in industry is breathtaking, covering pretty much any sector you can name. Although it is difficult to quantify, it is clear that planning via linear programming saves enormous amounts of the world's natural resources every day. In terms of money, a New York Times article by Gina Kolata states, "Solving linear programming problems for industry is a multibillion dollar-a-year business.'' Take that, Professor Hotelling.

The short book is devoted to the history, mathematics, and aesthetics of the salesman problem. If you like math, or you are just curious to learn how mathematicians are trying to understand the world around us, I hope you will have a look!

Learn more about the book and author at William Cook's webpage and the Princeton University Press website.

--Marshal Zeringue