“Paul Goldsman used the spacefilling curve heuristic to solve the same instance [15,112 cities in Germany]. Our solution was about 34% longer. At a leisurely 600 km of travel per day this means the time to drive our solution would be about 147 days versus 110 days for the solution of Bixby, Chvatal, and Cook. But our computation took less than a second on a cheap laptop, so here is the tradeoff: Use our heuristic and you get a reasonable route immediately. Alternatively, configure a network of 110 processors, then spend two months computing the shortest route to save a month of driving.”

Fascinating & accessible write-up on the use of spacefilling curves to solve the traditional traveling salesman problem. The researchers have already applied their technique to practical good use: routing blood for the Red Cross, delivery routes for Meals-on-Wheels and to target a space-based laser. (Ironic; life & death.)

If you’re at all interested in the history of programming languages, give this video a watch. You’ve got the father of APL, Ken Iverson himself, being interviewed along with a panel of experts.

If APL isn’t your cup of tea, then you can also watch for the crazy 70s flute music, the hardware, the fashion, the crazy hair & beards and the set design. This video is such a wonderful collection of stuff.

There’s more backstory at Catherine’s Myspace page. (And so you know, she’s working on a whole documentary on the history of APL and array programming.)