Quanta Magazine


Researchers soon started exploring how to apply this advance to the maximum flow problem. The idea is to imagine our highway network as a network of wires and to turn up the resistance on the highways that don’t have much available capacity, to discourage electrons from running through them. Because of Spielman and Teng, we can quickly calculate the flow of electricity through these wires, and it will have the rough attributes of the maximum flow of vehicles through the highways. (They won’t be exactly the same since the electrical flow problem doesn’t feature any hard limits on the capacities of the wires.)

Then, having produced this initial flow, you readjust the capacities just as in the combinatorial algorithms like Ford and Fulkerson’s. Next you reset the resistance of each wire to reflect these changed capacities and solve this new electrical problem, and so on.

Unlike the combinatorial approaches, which change one chunk of the network at a time, Spielman and Teng’s optimization approach takes in the entire sweep of the network at once. That makes each step more powerful, so you need fewer total steps to reach the maximum. In 2008, Samuel Daitch of Google and Spielman used this approach to essentially match the previous m1.5 bound for maximum flow. Then in 2013, Mądry pushed the approach further to break through the m1.5 barrier for low-capacity networks, speeding up the runtime to a multiple of about m1.43. “That was a shocker,” Rao said.

Over the following years, researchers extended this approach even further, but they got stuck at m1.33. They started to wonder if this exponent was a fundamental limit.

The fastest conceivable runtime for a maximum flow algorithm would just be a multiple of m (that is, m1.0), since it takes some multiple of m steps just to write down a network. This is referred to as linear time. But to many researchers, such a blazingly fast algorithm seemed unthinkable.

“There was no good reason to believe we could do that,” Spielman said.

Reduce, Reuse, Recycle

But the authors of the new paper felt there was more juice to squeeze out of Daitch and Spielman’s approach. Mądry had used it to reduce the number of steps needed to solve a maximum flow problem, but that reduction came at a price: At each step, the entire network had to be rewritten and its electrical flow solved from scratch.

This method treated Spielman and Teng’s algorithm as a black box — it didn’t matter what the algorithm was doing internally. The six researchers decided instead to dig into the guts of the algorithm and tailor its various components to the maximum flow problem. These components, they suspected, might even allow them to solve the harder “minimum cost” problem, in which you’re looking for the cheapest way to route a given amount of material. Computer scientists have long known that any minimum cost algorithm can solve the maximum flow problem as well.

As with other optimization approaches, the researchers came up with a notion of the “energy” of a flow — a function that considers the links’ costs and capacities. Shifting flow from an expensive, low-capacity link to a cheap, high-capacity link lowers the total energy of the system.

To figure out how to quickly move a flow toward a low-energy state, the researchers merged this optimization approach with the older combinatorial viewpoint. The latter, which changes only part of the network at a time, offers the potential of reusing some of your work from previous steps.

At each step the algorithm looks for a cycle — a path that starts and ends at the same point — that can reduce energy. The basic idea is simple: Imagine that you’ve created a flow that routes trucks from Chicago to New York along a toll road, but then you discover there’s a cheaper freeway available. Adding the cycle that starts in New York, runs to Chicago along the expensive road and comes back along the cheaper route effectively undoes the expensive path and replaces it with the cheaper one, reducing the total cost of the flow.

This approach uses many more steps than the electrical approach, so at first glance it “sounds like regressing,” said Valerie King of the University of Victoria in Canada. To compensate, at each step the algorithm must find a good cycle incredibly quickly — faster than it takes just to inspect the entire network.

That’s where the inner workings of Spielman and Teng’s algorithm come in. Their algorithm provides a novel way to use a “low-stretch spanning tree” — a sort of internal backbone that captures many of the network’s most salient features. Given such a tree, there’s always at least one good cycle you can build by adding a single link from outside the tree. So having a low-stretch spanning tree drastically reduces the number of cycles you need to consider.

Even then, for the algorithm to run quickly, the team couldn’t afford to build a brand new spanning tree at every step. Instead, they had to ensure that each new cycle caused only minor ripple effects in the spanning trees, so they could reuse most of their previous computations. Achieving this level of control was “the core difficulty,” said Yang Liu, a graduate student at Stanford University who is one of the paper’s authors.

Eventually, the researchers created an algorithm that runs in “almost linear” time, meaning that as you look at larger and larger networks, its runtime approaches some multiple of m. It’s a “tour de force,” Mądry said.

The algorithm uses many ideas from Spielman and Teng’s work, but it puts them together into something completely new. Looking at the algorithm is like encountering a car if you’ve only seen horse-drawn carriages, Spielman said. “I see it’s got a place to sit, I see it’s got wheels, I see it’s got something that makes it move. But they’ve replaced the horse with an engine.”

The team’s analysis is long and complicated, but other researchers will soon dive in to simplify things, Rao predicted. “My feeling is that it will all be made cleaner and better over the next few years,” he said.

Once the algorithm is streamlined, computer scientists will likely start using it as a subroutine in algorithms solving different problems, Spielman said. “Now that we know we can do this really quickly, people will find all sorts of applications for it that they just weren’t thinking of before.”

This dizzying speedup to the maximum flow problem has Spielman wondering about the other central problems in the theory of algorithms. “What else could we do?”


Source link