Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow

The maximum flow problem and its generalization, the minimum-cost flow problem, are classic combinatorial graph problems that find numerous applications in engineering and scientific computing. The highlight is accompanied by a commentary in a technical perspective from two-time Gödel prize winner Prof. Shang-Hua Teng of University of Southern California.

The paper "Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow" deals with the efficient calculation of maximum flows and minimum cost flows in networks. These problems involve an abstract notion of 'flow' in a network, but they can be used to model many problems on real-world networks, for example, routing traffic on roads or trains on railways, goods in supply infrastructures, or data in digital networks. Even the problem of identifying arbitrage opportunities in a trading market can be effectively modelled via minimum cost flow. Roughly speaking, flow problems deal with transporting as many units of 'flow' as possible in a given network with as low cost as possible. The maximum flow problem involves finding the most flow possible between two points in the network given constraints on how much flow each network connection can handle, while minimum cost flow problem additionally considers the minimization of transport costs.

As a mathematical challenge, the holy grail of flow research was the development of flow algorithms with running times that scale almost linearly with the size of the network, and this was finally achieved by the algorithm of Prof. Rasmus Kyng and Dr. Maximilian Probst Gutenberg and their co-authors. Fast running times are particularly important for the efficient handling of large and complex networks. Such algorithms could significantly improve the efficiency of solving network optimisation problems, especially in applications such as logistics, telecommunications and traffic planning. An almost-linear runtime would allow real-time applications and complex optimisation tasks in large-scale networks to be handled more effectively. For now, the new algorithms introduced by Prof. Kyng, Dr. Probst Gutenberg, and their co-authors remain impractical, as they rely on a theoretical analysis of algorithm performance on networks larger than anything even giant corporations like Google would ever consider. But, the race is now on to simplify and improve the algorithm to make it work well in practice.

The new algorithm managed to finally settle the running time of algorithms for flow problems that have been studied by computer scientists and mathematicians since the 1930s, if not before, pre-dating the establishment of computer science as a scientific discipline. The algorithm introduces a radically new approach to flow problems, by designing an algorithm that blends continuous optimization seamlessly with powerful new data structures for estimating distances and discovering 'local' ways to improve a solution using a striking new perspective on the geometry induced by a network.