ETH computer scientists write the fastest possible flow algorithm

Zurich – Computer scientists at the Swiss Federal Institute of Technology in Zurich (ETH) have developed an algorithm that calculates almost as fast as is possible. With this breakthrough, the maximum possible traffic flow with minimum transportation costs is calculated for any type of network.

Rasmus Kyng and his team at ETH have achieved a breakthrough that has been the subject of research for 90 years: Their network flow algorithm calculates the optimal and most cost-effective traffic flow for every type of network, whether rail, road, water or Internet. And above all, it does this so quickly that it presents the solution at the very moment a computer has read the data.

As the ETH explains in a report, until the turn of the millennium no algorithm was able to calculate faster than m1,5, where m stands for the number of connections in a network that the computer has to calculate. From 2004, it was possible to reduce the computing time required to solve the problem to m1,33. With Kyng's algorithm, the additional computing time required has now been reduced to virtually zero.

Kyng's doctoral supervisor Daniel A. Spielman, himself a pioneer in this field as a professor of mathematics and computer science at the elite American university Yale, described this groundbreaking algorithm as "absurdly fast". In the meantime, the researchers have reportedly refined their approach and developed further near-linear algorithms.

The latest algorithm was presented on June 27 at the Annual ACM Symposium on Theory of Computing. This also solves the minimum-cost-maximum-flow problem for networks that change gradually as new connections are added. In a second paper accepted by the IEEE Symposium on Foundations of Computer Science next October, the ETH researchers also present a further algorithm that also takes into account the removal of connections. ce/mm

View full article