Fetching the paper…
Reading the bibliography…
We give an $\widetilde{O}({m^{3/2 - 1/762} \log (U+W))}$ time algorithm for minimum cost flow with capacities bounded by $U$ and costs bounded by $W$.
Scaling algorithms for network problems
Harold N Gabow · 1983
Earlier work this paper cites.
Beyond the flow decomposition barrier
Andrew V Goldberg and Satish Rao · 1998
Earlier work this paper cites.
Faster approximate lossy generalized flow via interior point algorithms
Samuel I Daitch and Daniel A Spielman · 2008
Earlier work this paper cites.
Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
Paul Christiano, Jonathan A Kelner, Aleksander Mądry, Daniel A Spielman, and Shang-Hua Teng · 2011
Earlier work this paper cites.
A new approach to computing maximum flows using electrical flows
Yin Tat Lee, Satish Rao, and Nikhil Srivastava · 2013
Earlier work this paper cites.
Navigating central path with electrical flows: From flows to matchings, and back
Aleksander Mądry · 2013
Earlier work this paper cites.
Nearly maximum flows in nearly linear time
Jonah Sherman · 2013
Earlier work this paper cites.
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
Jonathan A Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford · 2014
Earlier work this paper cites.
Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow
Yin Tat Lee and Aaron Sidford · 2014
Cited alongside, same era.
Computing maximum flow with augmenting electrical flows
Aleksander Mądry · 2016
Cited alongside, same era.
Approximate undirected maximum flows in O ( m polylog n ) {O}(m\textnormal{ polylog }n) time
Richard Peng · 2016
Cited alongside, same era.
Negative-weight shortest paths and unit capacity minimum cost flow in O ~ ( m 10 / 7 log W ) \widetilde{O}(m^{10/7}\log{W}) time
Michael B Cohen, Aleksander Mądry, Piotr Sankowski, and Adrian Vladu · 2017
Cited alongside, same era.
Area-convexity, ℓ ∞ \ell_{\infty} regularization, and undirected multicommodity flow
Jonah Sherman · 2017
Cited alongside, same era.
Flows in almost linear time via adaptive preconditioning
Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang · 2019
Later among the works it cites.
Circulation control for faster minimum cost flow in unit-capacity graphs
Kyriakos Axiotis, Aleksander Mądry, and Adrian Vladu · 2020
Later among the works it cites.
Fully-dynamic graph sparsifiers against an adaptive adversary
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun · 2020
Later among the works it cites.
Unit capacity maxflow in almost O ( m 4 / 3 ) {O}(m^{4/3}) time
Tarun Kathuria, Yang P. Liu, and Aaron Sidford · 2020
Later among the works it cites.
Faster energy maximization for faster maximum flow
Yang P Liu and Aaron Sidford · 2020
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jonah Sherman · 2017
Cited alongside, same era.
Coordinate methods for accelerating ℓ ∞ \ell_{\infty} regression and faster approximate maximum flow
Aaron Sidford and Kevin Tian · 2018
Cited alongside, same era.
Fully dynamic spectral vertex sparsifiers and applications
David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng · 2019
Cited alongside, same era.
Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang · 2020
Later among the works it cites.
Fully dynamic electrical flows: Sparse maxflow faster than goldberg-rao
Yu Gao, Yang P Liu, and Richard Peng · 2021
Closest in time.
Minimum cost flows, mdps, and ℓ 1 \ell_{1} -regression in nearly linear time for dense instances
Jan van den Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang · 2021
Closest in time.