An algorithm that can calculate the maximum transport flow at the lowest cost and the fastest speed for all kinds of networks such as railroads, roads, and electricity has been born
A team of researchers led by Rasmus Kinn of the Swiss Federal Institute of Technology in Zurich has created a near-perfect algorithm to calculate the maximum transport flows at the lowest cost in any kind of network, be it rail, road or electricity, so fast that it is 'mathematically impossible to do any better.'
Researchers at ETH Zurich develop the fastest possible flow algorithm | ETH Zurich
A transportation flow algorithm is, for example, an algorithm that finds the fastest and cheapest route to transport as many goods as possible from Tokyo to Osaka. Kin's algorithm can quickly calculate the optimal transportation flow for all kinds of networks, including not only the transportation of goods by rail and road, but also water and the Internet.
Many researchers have worked on optimizing transportation flows in the past, but as networks become larger and more complex, the amount of calculations required increases explosively, making it impossible to perform calculations for networks of a certain size or larger.
In Kin's algorithm, the computational complexity is roughly proportional to the size of the network. In Landau notation, the computational complexity required for the network size m was O(m^1.5) until the 2000s, but in 2004 it became O(m^1.33), and in Kin's algorithm, the computational complexity approaches O(m) as the size of the network increases.
Since loading the network always requires linear time (O(m)), it is almost impossible to reduce the amount of computation any further, making it an 'almost perfect' algorithm.
When Kin's team published this algorithm in 2022, it was only applicable to fixed, static networks with directed connections, such as cities where all roads are one-way. However, the research team continued to work on it after the publication, and by 2024 it was possible to optimize networks that change over time and where new connections are added or removed.
With Kin's algorithm, all important network flow problems, including maximum flow and minimum cost problems, can now be treated as special cases of the minimum cost flow problem. Kin's ultra-fast algorithm is considered an important step in dealing with complex, data-intensive network problems that are dynamic and change very rapidly, such as molecular and brain networks in biology, as well as human friendships.
Related Posts:
