mlsanityData to 14 Oct 2026

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

arXiv 2203.00671 ↗First posted 1 Mar 2022cs.DScited by 28

Not on the map. Why?

Abstract (arXiv)

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 m1+o(1) time. Our algorithm builds the flow through a sequence of m1+o(1) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized mo(1) time using a new dynamic graph data structure. Our framework extends to algorithms running in m1+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.

Key facts. Cited by 28 papers in the map (data through 14 Oct 2026). First posted on arXiv 1 Mar 2022.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 5; 2024: 8; 2025: 5; 2026: 4.

28 papers.

Sort:

By area:

  1. 2023Scalable Optimal Transport Methods in Machine Learning: A Contemporary Surveycited by 27
  2. 2022Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictionscited by 16
  3. 2022Learning-Augmented Maximum Flowcited by 11
  4. 2024Testing Calibration in Nearly-Linear Timecited by 10
  5. 2024Parameter identification in linear non-Gaussian causal models under general confoundingcited by 5
  6. 2024Regularized Robustly Reliable Learners and Instance Targeted Attackscited by 5
  7. 2022Graph Neural Modeling of Network Flowscited by 3
  8. 2024Diversity-aware clustering: Computational Complexity and Approximation Algorithmscited by 3
  9. 2024Accelerating Matroid Optimization through Fast Imprecise Oraclescited by 3
  10. 2022Sublinear Algorithms for Hierarchical Clusteringcited by 2
  11. 2022A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignmentcited by 2
  12. 2024Warm-starting Push-Relabelcited by 2
16 more
  1. 2024A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clusteringcited by 2
  2. 2022Matching Map Recovery with an Unknown Number of Outlierscited by 1
  3. 2025Fair Clustering via Alignmentcited by 1
  4. 2026Robust Sublinear Convergence Rates for Iterative Bregman Projectionscited by 1
  5. 2026Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Meanscited by 1
  6. 2023Fair Correlation Clustering in Forestscited by 0
  7. 2023Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvaluescited by 0
  8. 2023An Analysis of On-the-fly Determinization of Finite-state Automatacited by 0
  9. 2023A Novel Skip Orthogonal List for Dynamic Optimal Transport Problemcited by 0
  10. 2024Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Bettercited by 0
  11. 2025Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulationcited by 0
  12. 2025Fast and Simple Densest Subgraph with Predictionscited by 0
  13. 2025Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Paircited by 0
  14. 2025A Differentiable Digital Twin of Distributed Link Scheduling for Contention-Aware Networkingcited by 0
  15. 2026Graph Alignment Topology as an Inductive Bias for Grounding Detectioncited by 0
  16. 2026A Near-Linear-Time Solver for Graph p-Laplacian Semi-Supervised Learning via Continuation in pcited by 0