Rasmus Kyng, ETH Zurich
Host: Dan Spielman
An Almost-Linear Time Algorithm for Maximum Flow and More
In this talk, I will explain a new algorithm for computing exact maximum and minimum-cost flows in almost-linear time, settling the time complexity of these basic graph problems up to subpolynomial factors.
Our algorithm uses a novel interior point method that builds the optimal flow as a sequence of approximate minimum-ratio cycles, each of which is computed and processed very efficiently using a new dynamic data structure.
By well-known reductions, our result implies almost-linear time algorithms for several problems including bipartite matching, optimal transport, and undirected vertex connectivity. Our framework also extends to minimizing general edge-separable convex functions to high accuracy, yielding the first almost-linear time algorithms for many other problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and isotonic regression.
This talk is based on joint work with Li Chen, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Our result appeared in FOCS’22 and won the FOCS best paper award.
Rasmus Kyng is an assistant professor of theoretical computer science at ETH Zurich. Before joining the department in 2019, he was a postdoctoral fellow and Harvard SEAS and the Simons Institute at UC Berkeley. In 2017, he received a PhD in computer science from Yale University, where he was advised by Daniel Spielman.
His work focuses on fast algorithms for solving graph problems, convex optimization, and structured linear equations. In addition, he develops hardness results for basic algorithmic problems and probability theoretic tools for algorithmic applications. His research has won the FOCS’22 best paper and FOCS’17 best student paper awards.