Need to rapidly transport goods across a country or speed the flow of web traffic? Take a souped-up algorithm for a test drive.
Finding the optimal route for moving stuff through a network is called the max flow problem, because you want the highest quantity flowing as quickly as possible. But the paths between nodes can have different capacities, like a wide highway versus a small country road. A max flow algorithm has to consider both the volume of flow and the route it can take.
The problem was first formulated in the 1950s by mathematicians working for the US Air Force, who used it in attempts to snarl the Soviet Union's rail network. "It has been studied for a long time," says Jonathan Kelner at the Massachusetts Institute of Technology. "The earliest algorithms were actually on these proto-computers – part person turning dials and part computers."
Every which way
Better computers and more efficient algorithms helped solve the problem faster. But existing algorithms still send flow through one path at a time, trying to find the best via trial and error. This gets trickier as the network gets larger. Kelner and his colleagues found a way to speed things up by representing paths as electrical resistors and flow as current. This allows the algorithm to use linear equations, which are faster to solve than the non-linear variety, so it can test multiple routes at once.
"It won't pick one path at a time, it will send electrical current along every possible way that it can," says Kelner.
The latest version of their algorithm works no matter how large the network. It identifies clusters and bottlenecks first, allowing the algorithm to focus on difficult areas and speed up the solution.
Independently, Jonah Sherman at the University of California, Berkley, has come up with a similar algorithm that works at the same speed. Neither of these algorithms has been demonstrated yet, but it should be possible to implement them in software in the next six months or so, says Kelner.
The algorithms actually solve a slightly simplified version of the max flow problem, called the approximate max flow problem. In this version, it is not possible to reach 100 per cent efficiency, but you can get a solution very near to it, notes Harald Räcke at the Technical University of Munich in Germany. "It's still a very good solution, and it's very fast," he says, making it useful for practical applications.
Journal reference: http://ift.tt/1jAu1Sr
If you would like to reuse any content from New Scientist, either in print or online, please contact the syndication department first for permission. New Scientist does not own rights to photos, but there are a variety of licensing options available for use of articles and graphics we own the copyright to.
