In a breakthrough reminiscent of Lucky Luke, the man who shoots faster than his shadow, Rasmus Kyng and his team have developed a super-fast algorithm that looks set to transform an entire field of research. Kyng's team's groundbreaking work includes what is known as a network flow algorithm, which addresses the question of how to achieve maximum flow in a network while minimizing transportation costs.
Imagine using the European transport network and looking for the fastest and cheapest route to transport as many goods as possible from Copenhagen to Milan. Kyng's algorithm can be applied in such cases to calculate the optimal and cheapest traffic flow for any type of network: be it rail, road, water or internet. His algorithm performs these calculations so quickly that it can provide the solution the moment a computer reads the data describing the network.
Calculations as fast as a network are large
Before Kyng, no one had ever managed to do that — although researchers have been working on the problem for about 90 years. Previously, it took significantly longer to calculate the optimal flow than to process the network data. And as the network became larger and more complex, the required computation time increased much faster, relatively speaking, than the actual size of the computational problem. That is why we also see flow problems in networks that are too large to be calculated by a computer.
Kyng's approach eliminates this problem: using his algorithm, computation time and network size increase at the same rate – a bit like when you take a walk and consistently maintain the same pace no matter how steep the path becomes. A look at the raw numbers shows how far we've come: until the turn of the millennium, no algorithm managed to calculate faster than M1.5Where M represents the number of connections in a network that the computer must calculate, and it only takes one time to read the network data M time. In 2004, the computational speed required to solve the problem was successfully reduced to M1.33. Using Kyng's algorithm, the 'extra' computational time required to reach the solution after reading the network data is now negligible.
Like a Porsche racing a horse-drawn carriage
The researchers at ETH Zurich have thus developed the theoretically fastest possible network flow algorithm. Two years ago, Kyng and his team presented the mathematical proof of their concept in a groundbreaking paper. Scientists refer to these new, almost optimally fast algorithms as “near-linear-time algorithms” and the community of theoretical computer scientists reacted to Kyng's breakthrough with a mixture of surprise and enthusiasm.
Kyng's doctoral supervisor, Daniel A. Spielman, a professor of applied mathematics and computer science at Yale and himself a pioneer and dean in the field, compared the “absurdly fast” algorithm to a Porsche passing horse-drawn carriages. In addition to winning the 2022 Best Paper Award at the IEEE Annual Symposium on Foundations of Computer Science (FOCS), their paper was also featured in the computer journal Communication from the ACMand the editorial staff of the popular science magazine Quantum named Kyng's algorithm one of the ten biggest discoveries in computer science in 2022.
The researchers at ETH Zurich have since refined their approach and developed further near-linear time algorithms. For example, the first algorithm focused on fixed, static networks whose connections are directional, meaning they function as one-way streets in urban road networks. The algorithms published this year are now also able to calculate optimal flows for networks that change incrementally over time. Lightning-fast computations are an important step in tackling very complex and data-rich networks that change dynamically and very quickly, such as molecules or the brain in biology, or human friendships.
Lightning-fast algorithms for evolving networks
On Thursday, Simon Meierhans, a member of Kyng's team, presented a new near-linear-time algorithm at the annual ACM Symposium on Theory of Computing (STOC) in Vancouver. This algorithm solves the maximum power, minimum cost problem for networks that change incrementally as new connections are added. Moreover, in a second paper accepted in October by the IEEE Symposium on Foundations of Computer Science (FOCS), the ETH researchers have developed another algorithm that also handles removing connections.
Specifically, these algorithms identify the shortest routes in networks where connections are added or removed. In real traffic networks, examples of such changes in Switzerland include the complete closure and then partial reopening of the Gotthard Base Tunnel in the months since summer 2023, or the recent landslide that destroyed part of the A13 motorway, which is the main alternative is. route to the Gotthard tunnel.
Faced with such changes, how does a computer, an online map service or a route planner calculate the cheapest and fastest connection between Milan and Copenhagen? Kyng’s new algorithms also calculate the optimal route for these incrementally or decrementally changing networks in near-linear time — so fast that the computation time for each new connection, whether added through rerouting or the creation of new routes, is again negligible.
But what exactly is it that makes Kyng’s approach to computation so much faster than any other network flow algorithm? In principle, all computational methods are faced with the challenge of having to analyze the network in multiple iterations to find the optimal flow and the route with minimum cost. In doing so, they go through each of the different variations where links are open, closed or congested because they have reached their capacity limit.
Calculate the whole? Or its parts?
Before Kyng, computer scientists usually chose between two main strategies to solve this problem. One was modeled on the railway network and involved computing an entire section of the network with an adjusted traffic flow in each iteration. The second strategy, inspired by power grid flows, computed the entire network in each iteration but used statistical averages for the adjusted flow of each section of the network to make the computation faster.
Kyng's team has now combined the respective advantages of these two strategies to create a radical new combined approach. “Our approach is based on many small, efficient, and cheap computational steps, which — together — are much faster than a few large ones,” says Maximilian Probst Gutenberg, a lecturer and member of Kyng's group who played a key role in developing the near-linear-time algorithms.
A brief look at the history of this field adds an extra dimension to the significance of Kyng's breakthrough: flow problems in networks were among the first to be solved systematically using algorithms in the 1950s, and flow algorithms played an important role in determining theoretical computer science as a research area in itself. The well-known algorithm developed by the mathematicians Lester R. Ford Jr. also dates from this period. and Delbert R. Fulkerson. Their algorithm efficiently solves the maximum throughput problem, which attempts to determine how to transport as many goods as possible through a network without exceeding the capacity of individual routes.
Fast and comprehensive
These advances showed researchers that the maximum flow problem, the minimum cost problem (transshipment or transportation), and many other important network flow problems can all be viewed as special cases of the general minimum cost flow problem. Before Kyng's work, most algorithms were only able to solve one of these problems efficiently, although they could not do so particularly quickly, and they could not be extended to the broader minimum cost flow problem. The same is true of the pioneering flow algorithms of the 1970s, for which theoretical computer scientists John Edward Hopcroft, Richard Manning Karp, and Robert Endre Tarjan each received the Turing Award, considered the “Nobel Prize” of computer science. Karp received his in 1985; Hopcroft and Tarjan won theirs in 1986.
Shift in perspective from railways to electricity
It wasn't until 2004 that mathematicians and computer scientists Daniel Spielman and Shang-Hua Teng — and later Samuel Daitch — managed to write algorithms that also provided a fast and efficient solution to the minimum-cost flow problem. It was this group that shifted the focus to energy flows in the electricity grid. Their shift in perspective from railways to electricity led to an important mathematical distinction: if a train is diverted on the railway network because a line is out of service, the next best route according to the timetable may already be taken by another train. In the electricity grid it is possible that the electrons that form an energy flow are partially diverted to a network connection through which another current already flows. Thus, unlike trains, the electric current can, in mathematical terms, be “partially” moved to a new connection.
This partial rerouting allowed Spielman and his colleagues to calculate such route changes much faster, while simultaneously recalculating the entire network after each change. “We rejected Spielman's approach of creating the most powerful algorithms we could for the entire network,” says Kyng. “Instead, we applied his idea of partial route computation to the earlier approaches of Hopcroft and Karp.” This computation of partial routes in each iteration played a major role in speeding up the overall flow computation.
A turning point in theoretical principles
Much of the progress made by ETH Zurich researchers is due to the decision to expand their work beyond the development of new algorithms. The team also uses and designs new mathematical tools that make their algorithms even faster. In particular, they developed a new data structure for organizing network data; this makes it possible to identify any change in a network connection extremely quickly; this in turn helps make the algorithmic solution so astonishingly fast. With so many applications ready for the near-linear time algorithms and for tools like the new data structure, the overall innovation spiral could soon be spinning much faster than before.
Yet laying the groundwork for solving very large problems that previously could not be computed efficiently is only one benefit of these significantly faster stream algorithms – because they also change the way computers compute complex tasks in the first place. “The past decade has seen a revolution in the theoretical foundations for obtaining provably fast algorithms for fundamental problems in theoretical computer science,” writes an international group of researchers from the University of California, Berkeley, including Rasmus Kyng and Deeksha Adil, a researcher at the Institute for Theoretical Studies at ETH Zurich.
