In a breakthrough that brings to mind Lucky Luke – the man who shoots faster than his shadow – Rasmus Kyng and his team have developed a superfast algorithm that looks set to transform an entire field of research. The groundbreaking work by Kyng’s team involves what is known as a network flow algorithm, which tackles the question of how to achieve the maximum flow in a network while simultaneously minimising transport costs.
Imagine you are using the European transportation network and looking for the fastest and cheapest route to move as many goods as possible from Copenhagen to Milan. Kyng’s algorithm can be applied in such cases to calculate the optimal, lowest-cost traffic flow for any kind of network – be it rail, road, water or the internet. His algorithm performs these computations so fast that it can deliver the solution at the very moment a computer reads the data that describes the network.
Computations as fast as a network is big
Before Kyng, no one had ever managed to do that – even though researchers have been working on this problem for some 90 years. Previously, it took significantly longer to compute the optimal flow than to process the network data. And as the network became larger and more complex, the required computing time increased much faster, comparatively speaking, than the actual size of the computing problem. This is why we also see flow problems in networks that are too large for a computer to even calculate.
Kyng’s approach eliminates this problem: using his algorithm, computing time and network size increase at the same rate – a bit like going on a hike and constantly keeping up the same pace however steep the path gets. A glance at the raw figures shows just how far we have come: until the turn of the millennium, no algorithm managed to compute faster than m1.5, where m stands for the number of connections in a network that the computer has to calculate, and just reading the network data once takes m time. In 2004, the computing speed required to solve the problem was successfully reduced to m1.33. Using Kyng’s algorithm, the “additional” computing time required to reach the solution after reading the network data is now negligible.
Like a Porsche racing a horse-drawn carriage
The ETH Zurich researchers have thus developed what is, in theory, the fastest possible network flow algorithm. Two years ago, Kyng and his team presented mathematical proof of their concept in a groundbreaking paper. Scientists refer to these novel, almost optimally fast algorithms as “almost-linear-time algorithms”, and the community of theoretical computer scientists responded to Kyng’s breakthrough with a mixture of amazement and enthusiasm.
Kyng’s doctoral supervisor, Daniel A. Spielman, Professor of Applied Mathematics and Computer Science at Yale and himself a pioneer and doyen in this field, compared the “absurdly fast” algorithm to a Porsche overtaking horse-drawn carriages. As well as winning the 2022 Best Paper Award at the IEEE Annual Symposium on Foundations of Computer Science (FOCS), their paper was also highlighted in the computing journal Communications of the ACM, and the editors of popular science magazine Quanta named Kyng’s algorithm one of the external pageten biggest discoveries in computer science in 2022.
The ETH Zurich researchers have since refined their approach and developed further almost-linear-time algorithms. For example, the first algorithm was still focused on fixed, static networks whose connections are directed, meaning they function like one-way streets in urban road networks. The algorithms published this year are now also able to compute optimal flows for networks that incrementally change over time. Lightning-fast computation is an important step in tackling highly 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 changing networks
On Thursday, Simon Meierhans – a member of Kyng’s team – presented a new almost-linear-time algorithm at the Annual ACM Symposium on Theory of Computing (STOC) in Vancouver. This algorithm solves the minimum-cost maximum-flow problem for networks that incrementally change as new connections are added. Furthermore, in a second paper accepted by the IEEE Symposium on Foundations of Computer Science (FOCS) in October, the ETH researchers have developed another algorithm that also handles connections being removed.
Specifically, these algorithms identify the shortest routes in networks where connections are added or deleted. In real-world 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 route to the Gotthard Road Tunnel.
Confronted with such changes, how does a computer, an online map service or a route planner calculate the lowest-cost and fastest connection between Milan and Copenhagen? Kyng’s new algorithms also compute the optimal route for these incrementally or decrementally changing networks in almost-linear time – so quickly that the computing time for each new connection, whether added through rerouting or the creation of new routes, is again negligible.