Network slowdowns could soon be a thing of the past, thanks to a superfast new algorithm.
The breakthrough offers a dramatically faster solution to a problem that has been plaguing computer scientists since the 1950s: maximum flow, or how to achieve the fastest flow of information through a system with limited capacity.
Previous maximum flow algorithms made steady and incremental advances, but they still took longer to find the optimal flow than to process the network data. But the new research, presented on June 11 at the Proceedings of the 56th Annual ACM Symposium on Theory of Computing, details an algorithm that can solve the problem roughly as quickly as it takes to write the details of the network down.
The maximum flow problem is a cornerstone of algorithmic science and has inspired many of the most significant advances in the field. The first attempt to solve it came in 1956, when the mathematicians Delbert Fulkerson and Lester Ford proposed what they called a "greedy solution" to the question.
Greedy algorithms work by making the most immediately advantageous choices at each point along the decision tree, picking the best path in front of it regardless of the routes this may block in the future.
Picture the problem of optimizing traffic moving from A to B along multiple possible paths, one route being made up of a first segment that is a six-lane highway and the final a three-lane road. To solve this, the greedy algorithm will launch as much traffic as possible (three lanes of cars) along the route, adjusting its capacity and repeating the same steps for other routes until every possible path is at full capacity.
Fulkerson and Ford's algorithm proved effective enough, but it often didn't produce the best possible flow: If other routes were cut off and suboptimal jams emerged, so be it. The subsequent 70 years of contributions to the problem attempted to refine this aspect of the solution, smoothing out unnecessary slow-downs by building better decision-making into the algorithm.
These tweaks shifted the runtime of the algorithm from a multiple m^2 (where m is the number of nodes in the network) to a multiple of m^1.33 in 2004, but then progress stalled.
To arrive at their breakthrough, the study researchers combined two prior approaches: the original solution that treated networks as traffic; and a later one that instead viewed them as an electrical grid. Unlike cars or trains, the flow of electrons can be partially diverted to join the current along another route, enabling computer scientists to map out the best flow across the entire network before the segment-by-segment traffic approach is applied.
Combining these two approaches resulted in a hybrid algorithm that was "absurdly fast," Daniel A. Spielman, a professor of applied mathematics and computer science at Yale University who supervised the doctoral program of one of the researchers, said in a statement. Spielman compared the new solution to previous ones as being like "a Porsche overtaking horse-drawn carriages."
Once refined, the new algorithm could potentially be applied to a number of applications, including internet data, airline scheduling and improving the efficiencies of markets, the researchers said.
