2026-07-26T04:50:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18054 2024-03-06T11:00:53Z ddc:004 open_access

An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk) Kyng, Rasmus Maximum flow Minimum cost flow Data structures Interior point methods Convex optimization 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 [Chen et al., 2022]. Our result appeared in FOCS'22 and won the FOCS best paper award. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rasmus Kyng 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.2 urn:nbn:de:0030-drops-180543 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.2 eng https://creativecommons.org/licenses/by/4.0/legalcode