Fetching the paper…
Reading the bibliography…
In this paper we present an $\tilde{O}(m\sqrt{n}\log^{O(1)}U)$ time algorithm for solving the maximum flow problem on directed graphs with $m$ edges, $n$ vertices, and capacity ratio $U$.
Theoretical improvements in algorithmic efficiency for network flow problems
Jack Edmonds and Richard M Karp · 1972
Earlier work this paper cites.
On finding a maximum flow in a network with special structure and some applications
Alexander V Karzanov · 1973
Earlier work this paper cites.
Network flow and testing graph connectivity
Shimon Even and R Endre Tarjan · 1975
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · 1984
Earlier work this paper cites.
Genuinely polynominal simplex and non-simplex algorithms for the minimum cost flow problem
James B Orlin · 1984
Earlier work this paper cites.
A strongly polynomial minimum cost circulation algorithm
Éva Tardos · 1985
Earlier work this paper cites.
An o (n 2 (m+ n log n) log n) min-cost flow algorithm
Zvi Galil and Éva Tardos · 1988
Earlier work this paper cites.
Finding minimum-cost circulations by successive approximation
Andrew V Goldberg and Robert E Tarjan · 1990
Earlier work this paper cites.
Network flows: theory, algorithms, and applications
Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin · 1993
Earlier work this paper cites.
A faster strongly polynomial minimum cost flow algorithm
James B Orlin · 1993
Earlier work this paper cites.
Interior-point polynomial algorithms in convex programming
Yurii Nesterov and Arkadii Semenovich Nemirovskii · 1994
Earlier work this paper cites.
Barrier functions and interior-point algorithms for linear programming with zero-, one-, or two-sided bounds on the variables
Robert M Freund and Michael J Todd · 1995
Earlier work this paper cites.
Approximating st minimum cuts in õ (n 2) time
András A Benczúr and David R Karger · 1996
Earlier work this paper cites.
Beyond the flow decomposition barrier
Andrew V. Goldberg and Satish Rao · 1998
Cited alongside, same era.
Better random sampling algorithms for flows in undirected graphs
David R Karger · 1998
Cited alongside, same era.
Random sampling in residual graphs
David Karger and Matthew Levine · 2002
Cited alongside, same era.
On the history of the transportation and maximum flow problems
Alexander Schrijver · 2002
Cited alongside, same era.
Introductory Lectures on Convex Optimization: A Basic Course
Yu Nesterov · 2003
Cited alongside, same era.
Combinatorial optimization: polyhedra and efficiency
Alexander Schrijver · 2003
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Later among the works it cites.
The multiplicative weights update method: a meta-algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
Later among the works it cites.
Iterative row sampling
Mu Li, Gary L Miller, and Richard Peng · 2012
Later among the works it cites.
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Closest in time.
A new approach to computing maximum flows using electrical flows
Yin Tat Lee, Satish Rao, and Nikhil Srivastava · 2013
Closest in time.
Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
Yin Tat Lee and Aaron Sidford · 2013
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Daniel A Spielman and Shang-Hua Teng · 2004
Cited alongside, same era.
Faster approximate lossy generalized flow via interior point algorithms
Samuel I Daitch and Daniel A Spielman · 2008
Cited alongside, same era.
Approaching optimality for solving SDD systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2010
Cited alongside, same era.
Fast approximation algorithms for cut-based problems in undirected graphs
Aleksander Madry · 2010
Cited alongside, same era.
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng · 2011
Cited alongside, same era.
A nearly-m log n time solver for sdd linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2011
Cited alongside, same era.
Closest in time.
Path finding i: Solving linear programs with \ \backslash ˜ o (sqrt(rank)) linear system solves
Yin Tat Lee and Aaron Sidford · 2013
Closest in time.
Navigating central path with electrical flows: from flows to matchings, and back
Aleksander Madry · 2013
Closest in time.
Max flows in o (nm) time, or better
James B Orlin · 2013
Closest in time.
An efficient parallel solver for sdd linear systems
Richard Peng and Daniel A Spielman · 2013
Closest in time.
Nearly maximum flows in nearly linear time
Jonah Sherman · 2013
Closest in time.
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
Closest in time.