Imagine a world where you can instantly find the best and cheapest way to move goods from Copenhagen to Milan using the European transportation network.
Thanks to a groundbreaking algorithm developed by Rasmus Kyng and his team, this is now a reality.
This superfast algorithm promises to transform the way we handle network flow problems, making calculations much quicker and more efficient.
Kyng’s team at ETH Zurich has developed a network flow algorithm that determines the maximum flow in a network while minimizing transport costs.
Whether it’s rail, road, water, or the internet, this algorithm can quickly calculate the optimal, lowest-cost traffic flow for any network.
Before Kyng’s breakthrough, solving these problems took much longer than reading the network data. As networks grew larger and more complex, the computing time increased significantly.
Kyng’s algorithm changes this by ensuring that computing time and network size increase at the same rate, making it much faster to compute solutions for large networks.
Before the turn of the millennium, no algorithm could compute faster than m^1.5, where m stands for the number of connections in a network.
By 2004, this was improved to m^1.33. Kyng’s algorithm has now made the “additional” computing time after reading the network data negligible, making it incredibly fast.
Kyng’s algorithm is recognized as the fastest possible network flow algorithm. It has received widespread acclaim, including the 2022 Best Paper Award at the IEEE Annual Symposium on Foundations of Computer Science (FOCS).
Popular science magazine Quanta named it one of the ten biggest discoveries in computer science in 2022.
Initially, Kyng’s algorithm focused on static networks with fixed connections. However, the latest versions can handle networks that change over time, such as traffic systems or even biological networks like molecules or the brain. These new algorithms can quickly compute optimal flows for networks where connections are added or removed, maintaining their speed and efficiency.
For example, in real-world traffic networks, changes like the closure and reopening of the Gotthard Base Tunnel or landslides affecting the A13 motorway in Switzerland can be efficiently managed by these algorithms. They can calculate the best routes despite these changes, ensuring minimal disruption.
Traditional methods for solving network flow problems involved either computing entire sections of the network with modified traffic flows or analyzing the entire network using average values. Kyng’s team combined the best aspects of both strategies. They use many small, efficient steps that, together, are much faster than a few large ones.
Flow problems in networks were some of the first to be systematically solved with algorithms in the 1950s. These algorithms played a crucial role in establishing theoretical computer science. The well-known algorithm by Lester R. Ford Jr. and Delbert R. Fulkerson efficiently solved the maximum-flow problem, which involves moving as many goods as possible through a network without exceeding capacity.
Most previous algorithms could only solve specific network flow problems efficiently, not the broader minimum-cost flow problem. Kyng’s research has made it possible to solve these problems quickly and efficiently.
In 2004, Daniel Spielman and his colleagues shifted the focus to power flows in electricity grids, enabling faster computations. Kyng’s team applied Spielman’s idea of partial route computation to earlier methods, significantly speeding up the overall process.
Kyng’s team didn’t just stop at developing new algorithms; they also created new mathematical tools. They developed a new data structure for organizing network data, allowing for rapid identification of changes in network connections. This innovation makes their algorithms even faster.
The almost-linear-time algorithms and new mathematical tools are set to revolutionize how computers handle complex tasks. These advancements lay the foundation for solving very large problems that were previously inefficient to compute.
Over the past decade, there has been a revolution in the theoretical foundations for obtaining provably fast algorithms for key problems in theoretical computer science. With researchers like Rasmus Kyng leading the way, we can expect to see even more significant advancements in the field.
