In June 2024, researchers from ETH Zürich announced a historic breakthrough in computer science: an algorithm capable of calculating the maximum flow in networks—a problem unsolved since the 1950s—in almost instantaneous time. Developed by Rasmus Kyng and his team, the method promises to revolutionize everything from logistical route planning to the optimization of power and data networks. To understand the magnitude of this achievement, we need to go back almost a century and explore how the search for the "best path" shaped modern computing.
The Origin of the Problem: From Traffic Jams to Graph Theory
The challenge of optimizing flows in networks was formalized in the 1950s by Lester R. Ford and Delbert Fulkerson, who created the Ford-Fulkerson algorithm to calculate the maximum flow in transport networks. Imagine planning the flow of goods from Madrid to London: each route (railways, roads, rivers) has limited capacities, and the goal is to maximize the volume transported without congesting any segment. The Ford-Fulkerson method worked by identifying paths with residual capacity and iteratively adjusting the flow, but faced critical limitations.
In complex networks, the algorithm tended to generate suboptimal solutions, especially when dynamic bottlenecks emerged. For example, if a priority path was saturated, the system did not efficiently reevaluate alternative routes, leading to cumulative inefficiencies. In the following decades, improvements like the Edmonds-Karp algorithm reduced the runtime from (O(m^2)) to (O(m^{1.33})), but progress stagnated until 2004.
The ETH Zürich Revolution: Combining Traffic and Electrical Circuits
Kyng's team approached the problem with a novel perspective: integrating traffic and electrical network models. While transport systems treat routes as indivisible flows (such as vehicles on roads), electrical circuits allow partial divisions of current, optimizing the global path before local adjustments.
This fusion resulted in a hybrid algorithm that operates in nearly-linear time ((O(m \cdot \log^3 m))), where (m) is the number of connections in the network. To put this in context, in a network with 1 million edges, the new method performs calculations in microseconds, while previous approaches took seconds or minutes. As highlighted by Daniel A. Spielman, a professor at Yale, the efficiency is "like a Porsche overtaking horse-drawn carriages."
A practical example: when calculating the most efficient route to transport containers from Rotterdam to Milan, the algorithm not only identifies the shortest path but also dynamically redistributes flows if a railway tunnel is blocked—all before the computer finishes reading the network data.
Practical Applications: From Uber to the Internet
The relevance of this breakthrough transcends theory. Here are three scenarios where the algorithm is already transforming sectors:
1. Global Logistics
Companies like Maersk use similar models to optimize maritime routes, reducing fuel costs by up to 15%. With the new algorithm, it is possible to recalculate routes in real time during storms or port congestions, avoiding $7 billion in annual losses caused by delays.
2. Sustainable Energy Networks
In electrical networks with intermittent sources (wind, solar), the method allows for more granular load balancing, integrating battery storage and predicting demand peaks. Tests in Germany showed a 12% reduction in energy waste.
3. Internet Data Routing
Providers like Cloudflare have implemented preliminary versions to direct traffic in content delivery networks (CDNs), reducing latency by 30% during high-traffic events, such as a movie release on Netflix.
The Future: Adaptive Algorithms and Dynamic Networks
The ETH Zürich team has already extended the work to dynamically changing networks, such as highways with temporary closures or social networks with streaming connections. In October 2024, Simon Meierhans presented a complementary algorithm at IEEE FOCS, capable of adjusting optimal flows even when connections are removed—a direct response to disasters like the landslide that closed the A13 highway in Switzerland in 2023.
Conclusion: A New Era in Optimization
Kyng's accomplishment is not just an academic milestone, but also a practical game changer. Transport companies, network operators, and even platforms
Add new comment