A long exposure shot of traffic on a road at night in Toulouse, France. (Image credit: Alamy)
Network lag issues could soon be a thing of the past thanks to a new super-fast algorithm.
The breakthrough offers a significantly more efficient solution to a problem that has plagued computing scientists since the 1950s: flow maximization, or how to ensure that information moves as quickly as possible through a system with limited bandwidth.
Previous max-flow algorithms have made steady, slow progress, but they still take longer to find the optimal flow than to process the network data. But new research presented June 11 at the 56th annual ACM Symposium on Theory of Computing describes an algorithm that can solve the problem in about the same amount of time it takes to write the network characteristics.
The max-flow problem is a fundamental problem in the field of algorithmic science and has inspired many of the most significant advances in the discipline. The first attempt to solve it was in 1956, when mathematicians Delbert Fulkerson and Lester Ford proposed what they called a “greedy solution” to the problem.
Greedy algorithms operate by making the most profitable decision at each step of the decision tree, choosing the best path forward, regardless of routes that may be blocked in the future.
Imagine the problem of optimizing a route from point A to point B via several possible paths, one of which includes the first segment being a six-level highway and the last segment being a three-level road. To solve this problem, a greedy algorithm would push as much traffic (three lanes of cars) as possible along this route, adjusting its capacity and repeating the same actions for the other routes until each of the possible paths is completely loaded.
Fulkerson and Ford's algorithm was quite efficient, but it often did not provide the best possible flow: if other routes were blocked and suboptimal congestion occurred, it was inevitable. Over the next 70 years, researchers tried to improve this aspect of the solution, minimizing unnecessary delays by introducing more efficient decision-making methods into the algorithm.
These changes increased the running time of the algorithm from a multiple of m^2 (where m is the number of nodes in the network) to a multiple of m^1.33 in 2004, but then progress slowed.
To achieve their breakthrough, the researchers combined two previous approaches: an initial solution that treated networks as transportation networks, and a later one that analyzed them as an electrical grid. Unlike cars or trains, the flow of electrons can be partially rerouted to connect to another route, allowing scientists to map the best flow across the entire network before applying the segment-by-segment transportation approach.
Merging the two approaches produced a hybrid algorithm that was “ridiculously fast,” said Daniel A. Spielman, a professor of applied mathematics and computer science at Yale who supervised the doctoral program of one of the researchers. Spielman compared the new solution to previous ones, calling it “a Porsche outrunning horse-drawn carriages.”
Once refined, the new algorithm could be applied to a variety of areas, including internet traffic, airline flight planning and improving market efficiency, the researchers said.
Ben TurnerNavigate Social LinksSenior Staff Writer
Ben Turner is a Live Science staff writer based in the U.K. He covers physics, astronomy, and other topics.
Sourse: www.livescience.com
