HackerPapers

arXiv:2203.00671cs.DS

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

Abstract

We give 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.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 9 identifiable commenters in 9 comments across 6 threads, from Jun 2022 to Jun 2024. Found in 3 HN submissions from Mar 2022 to Apr 2022. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments6 threads

  1. Researchers develop the fastest possible flow algorithm 1 comment

    • That's because even the ACM link is an abbreviation of the actual paper. Preprint at https://arxiv.org/abs/2203.00671 (Pages 68-75 build up the full details of the bound, which looks something like Õ(mκ⁻²α⁻²ϵ⁻¹). There are enough details over the preceding dozens of pages that I…

      vitusView on HNParent context

  2. Historic algorithms help unlock shortest-path problem breakthrough 1 comment
  3. Ask HN: What is new in algorithms and data structures these days? 1 comment

    • For Maximum Flow (and Minimal Cut) through flow network we are getting close to linear time: 2022 Paper https://arxiv.org/abs/2203.00671

      sireatView on HNParent context

  4. Ask HN: What's new in theoretical CS these days? 1 comment

    • Maximum Flow and Minimum-Cost Flow in Almost-Linear Time https://news.ycombinator.com/item?id=31675015 https://arxiv.org/abs/2203.00671

      gfdView on HNParent context

  5. Why SAT Is Hard 1 comment

    • If it’s NP it’s polynomially reducible to SAT. There are problems that do not admit a polynomial reduction to SAT, but by Cook-Levin they’re not in NP. It is of course possible to construct a problem that will require strictly more steps than the most efficient algorithm for…

      eynshamView on HNParent context

  6. Researchers achieve ‘absurdly fast’ algorithm for network flow 4 comments

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.