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. Over the years, these two problems have inspired many of the biggest advances in algorithmic techniques. “They’re almost why we have a field of algorithms,” Spielman said.

The new algorithm solves these two problems in “almost linear” time, which means that the algorithm’s runtime is roughly proportional to the amount of time it takes merely to write down the details of the network in the first place. No other algorithm for these problems comes close to running this fast for all possible networks. The result made him “jump up and down,” said Satish Rao of the University of California, Berkeley. “It’s amazing.”

For now, it’s primarily a theoretical advance, since the speed improvements kick in only for networks that are far larger than the ones we encounter in the real world, for which maximum flow problems can already be solved fairly quickly (at least, if they don’t involve minimizing costs). But pieces of the new algorithm might see practical use within a year, predicted Richard Peng of the University of Waterloo in Canada, one of the algorithm’s six creators. And in the coming years, researchers said, computer scientists will likely find ways to make it more practical and perhaps even slightly faster.

Even if improvements do come along, though, this new paper is the “slam dunk,” said Aleksander Mądry of the Massachusetts Institute of Technology. It’s “essentially the best possible,” he said.

One Path at a Time

So many computer scientists have studied maximum flow that conference talks about past work look like the credits after a movie, Peng said. But most people date the first formal algorithm to 1956, when Lester Ford and Delbert Fulkerson solved maximum flow using what’s called a “greedy” approach — one that, at every step, uses the objects that come most easily to hand.

To understand this approach, imagine a network of highways on which you’d like to send as many delivery trucks as possible from Los Angeles to New York City in a given amount of time. Ford and Fulkerson’s algorithm starts by choosing one path from LA to New York and routing as many trucks along it as possible. This typically won’t take advantage of the full capacity of all the roads on that particular path: If one segment of your path is a five-lane highway but it leads into a two-lane bridge, you can launch only two trucks at any moment.

Next, the algorithm revises the capacities of these segments to reflect that you’ve now used some of their capacity: It subtracts the number of trucks you sent from the capacities of the segments, so the five-lane highway now only has a capacity of 3 and the two-lane bridge has a capacity of zero. At the same time, the algorithm adds 2 to the capacities of these highways in the reverse direction, so we can undo some of this flow later if we wish.

The algorithm then finds a new path from LA to New York that has room for some trucks, sends as many trucks along it as possible, and updates capacities again. After a finite number of these steps, there will be no path from LA to New York that can accept any more trucks, and then we’re done — we just combine all the flows we’ve constructed, and we have the maximum possible flow through the network.

Merrill Sherman/Quanta Magazine

Ford and Fulkerson’s algorithm doesn’t try to make smart choices along the way. If it chooses a path that cuts off other useful routes, that’s just a problem it deals with later. In the decades that followed the algorithm’s publication, researchers tried to speed up the runtime by having the algorithm make more judicious choices — such as always using the shortest available path or the one with the most available capacity.

In 1970, Yefim Dinitz found an efficient way to use all the shortest paths in the network in a single step. This created an algorithm whose runtime, in networks with low capacities, was shown by Shimon Even and Robert Tarjan to be a multiple of m1.5, where m is the number of links in the network. (The Ford-Fulkerson algorithm, by comparison, takes a multiple of m2 steps in low-capacity networks.) Almost 30 years later, Rao and Andrew Goldberg, who is now at Amazon, produced similar results for networks with high capacities. But no one could beat the 1.5 exponent. “Coming into the 2000s … this m1.5 barrier was entrenched,” said Sushant Sachdeva of the University of Toronto, one of the new paper’s authors.

To make progress, computer scientists would have to take an entirely different approach.

From Combinations to Calculus

So far, all these algorithms employed combinatorial approaches, which look for some type of structure at each step and use that structure to update the flow. But in 2003, Spielman and Shang-Hua Teng of the University of Southern California opened the door to a radically different “optimization” approach, in which you use techniques from calculus to guide you toward an optimal solution.

Spielman and Teng developed a fast optimization algorithm that solves not the maximum flow problem, but the closely related problem of finding the lowest-energy electrical flow through a network of wires that each have a given resistance. Spielman and Teng’s advance was “a key moment,” said Sachdeva.