computer science

Science
10:25 am
Tue August 6, 2013

The Water Delivery Man Problem

Optimal route for the 33-city traveling salesman problem in the 1962 Car 54 contest. Proctor & Gamble sponsored a $10,000 grand prize for the winning entry. Mathematicians Robert Karg and Gerald Thompson tied for first place.
Credit Bill Cook / In Pursuit of the Traveling Salesman

There is a problem that has vexed mathematicians for the greater part of the past century. Currently, there is no solution, and nobody knows for certain whether or not one exists. But cracking the code would be a huge breakthrough both in theoretical mathematics and practical everyday applications. Ellis Robinson brings the story, starting with a description of the problem from physicist Eddie Farhi.

Read more