“Maximum flow has been studied since the 1950s, when it was formulated to study the Soviet railway system.”
Seventy years on one of the oldest problems in computing, and the new algorithm runs in roughly the time it takes to write the network down. Yale’s Daniel Spielman said he didn’t believe an algorithm this good could exist. One of the authors is a Stanford grad student. The ceiling everyone assumed was real turned out to be a lack of imagination.