William J. “Bill” Cook, Chandler Family Chair and professor in the Stewart School of Industrial and Systems Engineering, and author of In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (January 2012), recently wrote an article for The New York Times titled “The Problem of the Traveling Politician.”
The traveling-salesman problem is one of the great unsolved problems in mathematics, capturing notions of complexity that are at the core of the information age. Using deep theory developed in the 1960s, an efficient method for solving the T.S.P. would provide an efficient method for solving any computational problem for which it is easy to verify that an answer is correct. Most mathematicians expect this to be impossible, but no one knows for sure.
In the article, Cook uses the traveling salesman problem, a specialty of his, to suggest optimal travel routes that will save time and gasoline for those politicians who are preparing to hit the campaign trail.
To see Cook’s suggested routes, and read the article in full, click here