CarTalk.com Best of Deals Car Reviews Repair Shops Cars A-Z Radio Show

$1M Prize for Solution of Traveling Salesman Problem

"Meanwhile, the Clay Mathematics Institute is offering a $1 million prize to anyone who can show whether the Traveling Salesman Problem can be fully solved at all, which the mathematician Jordan Ellenberg recently called “the biggest open problem in complexity theory.”

NYT: March 14 - The Traveling Salesman Problem

See what can be found in the Theatre Section of the New York Times? And you thought it was for egg-head liberals.

I suspect that the article may have oversimplified what is needed to win the prize, unless the Clay Institute is currently offering TWO one million dollar prizes. But that’s the NYT for you.

The diagram obviously shows a solution (not necessarily the best solution) to a problem different from the one that was a recent Car Talk Puzzler. The only point in New England appears to be Boston, which means at least four states aren’t on the route in that part of the country. It also misses both Nevada and New Mexico entirely, and has two points in California. (That’s just the parts of the country I can speak for without seeing state lines on the map.)

The diagram shows a solution for an optimal tour through 33 cities in a 1962 Procter and Gamble contest. Yes, it is optimal.

If you did not read the article, you should not criticize.



BTW, companies like MapQuest calculate and store in data bases the shortest distances between thousands of US cities. In that way they have converted a problem like the TSP which requires exponentially increasing computer time as the number of cities increases into a problem which increases in polynomial fashion with number of cities. The secret to all clever optimization problems is to avoid recomputing and to store data on the fly to be used later.

If one is interested, one could listen in to the MIT open courseware classes which are filmed MIT undergraduate classes. (It’s a bit hokey, as you will see for yourself if you watch, but it is interesting if one has the time and curiosity.) A discussion of optimization problems in general and the 0/1 Knapsack problem in particular starts at

If you want someone to read the article before commenting on the difference between the graphic you posted and the recent Car Talk Puzzler, you shouldn’t have posted the graphic. If you think that was criticism, your definition of criticism is overbroad.