Erica Klarreich in Quanta:
A team of computer scientists has come up with a dramatically faster algorithm for one of the oldest problems in computer science: maximum flow. The problem asks how much material can flow through a network from a source to a destination if the links in the network have capacity limits.
The new algorithm is “absurdly fast,” said Daniel Spielman of Yale University. “I was actually inclined to believe … algorithms this good for this problem would not exist.”
Maximum flow has been studied since the 1950s, when it was formulated to study the Soviet railway system. “It’s older than maybe the theory of computer science,” said Edith Cohen of Google Research in Mountain View, California. The problem has many applications: internet data flow, airline scheduling and even matching job applicants to open positions. The new paper handles both maximum flow and a more general version of the problem in which you also want to minimize costs.
More here.