Pioneering math researcher returns to Waterloo

Mathematics Professor Bill Cook may not have taken the shortest route to return to his alma mater, but he’s back now.

“I think this is the best place in the world to be studying the material I enjoy so much,” says Cook, a Waterloo math alumnus who went on to teach at universities around the world before returning to Waterloo.  He is back as a professor to the school where he received his PhD in Combinatorics and Optimization in 1983.

Cook is best known for his pursuit of the Travelling Salesman Problem (TSP), which attempts to plot the shortest distance between a set of locations. Last year, his book, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, was released.

Cook’s own academic roadmap has featured a number of impressive stops, including Georgia Tech where he was the Chandler Family Chair, the University of Bonn where he was an Alexander von Humboldt Research Fellow, as well as positions at Cornell, Columbia, Bellcore, Rice, and Princeton.  This fall he’ll be teaching 110 Waterloo undergraduates about optimization, as well as continuing his theoretical journey with the TSP.

Research has many applications

Beyond its literal use to plot the most efficient distances between a large number of locations, Cook says that the Travelling Salesman Problem is a benchmark for how well we understand complexity in many fields.

One of the most exciting uses is in genetics. “My computer code is used for genetic sequencing of DNA—that’s the salesman problem. In the TSP you’re trying to order cities, and in the sequencing problem you’re trying to map the order of DNA in nature,” he says. Other fields where the problem is applied are equally diverse, such as the mechanical challenge of determining which order to drill the holes in a circuit board, or the order by which to view a set of stars when trying to maximize use of a telescope.

While most believe that there’s a point past which the TSP calculation is impossible, Cook’s goal is to constantly push that limit. Already, an iPhone app allows users to calculate the best routes between up to 500 locations, but beyond 10, 000 is where Cook says the calculation starts to become really unwieldy. From July 4, 2012 to July 4, 2013, he held a contest offering a $500 prize for the best route between every town in the United States:  115,475 locations.

Back in Waterloo, his old department is pleased to welcome Cook into their fold. “The Combinatorics and Optimization department is thrilled to have Bill Cook as a colleague,” says chair Alfred Menezes. “Bill's presence will be instrumental in upholding our strong record of research excellence in discrete optimization. He is also a fantastic teacher and lecturer.”