The maximum-flow problem, or max flow, is one of the most basic problems in computer science: first solved during preparations for the Berlin airlift, it’s a component of many logistical problems and a staple of introductory courses on algorithms. Now MIT researchers, with colleagues at Yale and the University of Southern California, have demonstrated the first improvement of the algorithm in 10 years.
The max-flow problem is, roughly speaking, to calculate the maximum amount of “stuff” that can move from one end of a network to another, given the capacity limitations of the network’s links. The stuff could be data packets traveling over the Internet or boxes of goods traveling over the highways; the links’ limitations could be the bandwidth of Internet connections or the average traffic speeds on congested roads.
But the algorithm has applications outside network analysis, explains Jonathan Kelner, an assistant professor of applied mathematics at MIT, who helped lead the work. “A very, very large number of optimization problems, if you were to look at the fastest algorithm right now for solving them, use max flow,” Kelner says. Examples might include airline scheduling, circuit analysis, task distribution in supercomputers, digital image processing, and the assembly of DNA sequences.
Don’t settle for half the story.
Get paywall-free access to technology news for the here and now.
