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.
10 Breakthrough Technologies 2024
Every year, we look for promising technologies poised to have a real impact on the world. Here are the advances that we think matter most right now.
AI for everything: 10 Breakthrough Technologies 2024
Generative AI tools like ChatGPT reached mass adoption in record time, and reset the course of an entire industry.
Scientists are finding signals of long covid in blood. They could lead to new treatments.
Faults in a certain part of the immune system might be at the root of some long covid cases, new research suggests.
What’s next for AI in 2024
Our writers look at the four hot trends to watch out for this year
Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.