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.
Traditionally, Kelner explains, algorithms for calculating max flow would consider one path through a network at a time. If the path had unused capacity, the algorithm would simply send more stuff over it and see what happened.
But Kelner and his colleagues have taken a fundamentally new approach to the problem. They represent a network as a matrix, which is math speak for a big grid of numbers. Each node in the network is assigned one row and one column of the matrix; the number where a row and a column intersect represents the amount of stuff that may be transferred between two nodes.
In the branch of mathematics known as linear algebra, a row of a matrix can also be interpreted as a mathematical equation. Since the tools of linear algebra make it possible to simultaneously solve all the equations embodied by all a matrix’s rows, the new algorithm effectively evaluates all the paths through the network at once. For a network like the Internet, with billions of nodes, it could thus solve the max-flow problem hundreds of times faster than its predecessor.
This artist is dominating AI-generated art. And he’s not happy about it.
Greg Rutkowski is a more popular prompt than Picasso.
This nanoparticle could be the key to a universal covid vaccine
Ending the covid pandemic might well require a vaccine that protects against any new strains. Researchers may have found a strategy that will work.
How do strong muscles keep your brain healthy?
There’s a robust molecular language being spoken between your muscles and your brain.
The 1,000 Chinese SpaceX engineers who never existed
LinkedIn users are being scammed of millions of dollars by fake connections posing as graduates of prestigious universities and employees at top tech companies.
Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.