{"id":"doi:10.1145/3728631","kind":"article","title":"Maximum Flow and Minimum-Cost Flow in Almost-Linear Time","authors":["Li Chen","Rasmus Kyng","Yang P. Liu","Richard Peng","Maximilian Probst Gutenberg","Sushant Sachdeva"],"author_count":6,"year":2025,"published":"2025-04-09","venue":"Journal of the ACM","cited_by":22,"doi":"10.1145/3728631","arxiv_id":null,"nct_id":null,"source_url":"https://doi.org/10.1145/3728631","archive_url":"https://space-kitty.com/papers/doi:10.1145/3728631","updated":null,"pmid":null,"pmcid":null,"openalex_id":"W4409280356","pdf_url":"https://dl.acm.org/doi/pdf/10.1145/3728631","abstract":"We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in \\(m^{1+o(1)}\\) time. Our algorithm builds the flow through a sequence of \\(m^{1+o(1)}\\) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized \\(m^{o(1)}\\) time using a new dynamic graph data structure. Our framework extends to algorithms running in \\(m^{1+o(1)}\\) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p -norm flows, and p -norm isotonic regression on arbitrary directed acyclic graphs.","abstract_license":"CC-BY (publisher license, via OpenAlex)","license":"cc-by","is_open_access":true,"retracted":false,"peer_reviewed":null,"categories":["Complexity and Algorithms in Graphs"],"details":null,"provenance":"openalex","attribution":"Abstract of \"Maximum Flow and Minimum-Cost Flow in Almost-Linear Time\" by Li Chen, Rasmus Kyng, Yang P. Liu et al., https://doi.org/10.1145/3728631, used under its Creative Commons Attribution license (CC-BY); markup removed, otherwise unmodified.","topics":[{"slug":"algorithms-complexity","name":"Algorithms & Complexity Breakthroughs","domain_slug":"math-cs"}],"cited_in_dossiers":[]}