Technology
'Absurdly fast' algorithm solves 70-year-old logjam — speeding up network traffic in areas from airline scheduling to the internet
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.
Related: New quantum computer smashes 'quantum supremacy' record by a factor of 100 — and it consumes 30,000 times less power
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.
-
Technology3h ago
Trump and Harris are sharply divided on science, but share common ground on US technology policy
-
Technology3h ago
Physics Nobel awarded to neural network pioneers who laid foundations for AI
-
Technology5h ago
Internet slowdown to be resolved soon: PTA
-
Technology5h ago
IST kicks off 'World Space Week' in Islamabad
-
Technology7h ago
Just launched, and already in a Prime Day fitness tracker deal? Has Samsung lost it?
-
Technology7h ago
We recommend this Prime Day smartwatch deal: Now at its cheapest-ever price
-
Technology8h ago
Some Top AI Labs Have ‘Very Weak’ Risk Management, Study Finds
-
Technology8h ago
OpenAI Chief Technology Officer Mira Murati and Two Other Top Execs Leave Company