An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

DOI10.1137/1.9781611973402.16zbMath1423.05177arXiv1304.2338OpenAlexW2278710066WikidataQ56018625 ScholiaQ56018625MaRDI QIDQ5383975

Jonathan A. Kelner, Aaron Sidford, Yin Tat Lee, Lorenzo Orecchia

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.2338

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (32)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Lower Bounds for Parallel and Randomized Convex Optimization ⋮ Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ Computing Weighted Strength and Applications to Partitioning ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration ⋮ Hypergraph Cuts with General Splitting Functions ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Minimum cost flow in the CONGEST model ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Hardness Results for Structured Linear Systems ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods ⋮ Efficient Convex Optimization with Oracles ⋮ Alternating minimization methods for strongly convex optimization ⋮ Lower bounds for in-network computation of arbitrary functions ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent ⋮ Fast Augmenting Paths by Random Sampling from Residual Graphs ⋮ Generalized Momentum-Based Methods: A Hamiltonian Perspective ⋮ Unnamed Item ⋮ Near-Optimal Distributed Maximum Flow

This page was built for publication: An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations