CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Conférence grand public
Président: Gena Hahn (Université de Montréal)

BILL COOK, University of Waterloo
The traveling salesman problem: postscards from the edge of impossiblity  [PDF]

Given $n$ points, the TSP asks for the shortest route to visit them all. Simple enough. But even a whisper of the problem strikes fear in the heart of the computing world. Last year, a Washington Post article reported it would take "1,000 years to compute the most efficient route between 22 cities."

In an ultimate battle of math versus the impossible, the impossible wins: it is likely no TSP solution method can have good performance on every data set as the number of points $n$ goes off to infinity. That said, the 1,000-year claim ignores over 70 years of intense mathematical study. A 22-city TSP can be handled in a snap with modern techniques, even on an iPhone. Going larger, examples with nearly 50,000 points and Google Map walking distances have been solved to precise optimality. And if we have a couple of million points to visit, say the nearest stars to our sun, then my money is on the math. Indeed, for this particular example, with 2,079,471 stars, we have a route that is guaranteed to be no more than 1.00002 times longer than a shortest possible solution. A few new ideas, perhaps from members of the audience, could nail down the optimal star tour.

Complexity theory suggests there are limits to the power of general-purpose computational techniques, in science and elsewhere. But what are these limits and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this context, demonstrating whether or not focused efforts on a single, possibly unsolvable, problem will produce results beyond our expectations.