Unit Capacity Maxflow in Almost $m^{4/3}$ Time

DOI10.1137/20M1383525OpenAlexW4224133915MaRDI QIDQ5071088

No author found.

Publication date: 20 April 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1383525

zbMATH Keywords

optimizationinterior point methodsmaximum flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Generalized cut trees for edge-connectivity ⋮ Fast algorithms via dynamic-oracle matroids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Random Sampling in Cut, Flow, and Network Design Problems
• Runtime guarantees for regression problems
• Beyond the flow decomposition barrier
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Network Flow and Testing Graph Connectivity
• Approximate Undirected Maximum Flows in O(mpolylog(n)) Time
• Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m^10/7 log W) Time (Extended Abstract)
• Approximate Max-Flow on Small Depth Networks
• Area-convexity, l _∞ regularization, and undirected multicommodity flow
• Solving tall dense linear programs in nearly linear time
• Faster energy maximization for faster maximum flow
• Faster p-norm minimizing flows, via smoothed q-norm problems
• Flows in almost linear time via adaptive preconditioning
• Solving linear programs in the current matrix multiplication time
• An homotopy method for l _p regression provably beyond self-concordance and in input-sparsity time
• Iterative Refinement for ℓ_p-norm Regression
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Faster approximate multicommodity flow using quadratically coupled flows
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
• A new approach to computing maximum flows using electrical flows
• Max flows in O(nm) time, or better
• Minimum cost flows, MDPs, and ℓ ₁ -regression in nearly linear time for dense instances

This page was built for publication: Unit Capacity Maxflow in Almost $m^{4/3}$ Time