Fetching the paper…
Reading the bibliography…
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 $m^{1+o(1)}$ time.
“Solving Linear Programs with Sqrt(rank) Linear System Solves”
Yin Lee and Aaron Sidford · 1910
Earlier work this paper cites.
“Application of the simplex method to a transportation problem”
George Dantzig · 1951
Earlier work this paper cites.
“Maximal Flow through a Network.”
L.. Ford and D.. Fulkerson · 1954
Earlier work this paper cites.
“An out-of-kilter method for minimal-cost flow problems”
Delbert Fulkerson · 1961
Earlier work this paper cites.
“Algorithm for solution of a problem of maximum flow in networks with power estimation”
E.A. Dinic · 1970
Earlier work this paper cites.
“Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems”
Jack Edmonds and Richard. Karp · 1972
Earlier work this paper cites.
“Metod porazryadnogo sokrashcheniya nevyazok i transportnye zadachi” In Russian. Title translation: Excess scaling and transportation problems
E.A. Dinic · 1973
Earlier work this paper cites.
“An $n{̂5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs”
John. Hopcroft and Richard. Karp · 1973
Earlier work this paper cites.
“On finding maximum flows in networks with special structure and some applications”
Alexander Karzanov · 1973
Earlier work this paper cites.
“Network Flow and Testing Graph Connectivity”
Shimon Even and R. Tarjan · 1975
Earlier work this paper cites.
“An O ( E V log 2 V ) O(EV\log^{2}V) Algorithm for the Maximal Flow Problem”
Zvi Galil and Amnon Naamad · 1980
Earlier work this paper cites.
“A data structure for dynamic trees”
Daniel Sleator and Robert Tarjan · 1983
Earlier work this paper cites.
“A New Polynomial-Time Algorithm for Linear Programming”
Narendra Karmarkar · 1984
Earlier work this paper cites.
“Scaling Algorithms for Network Problems”
Harold. Gabow · 1985
Earlier work this paper cites.
“A Strongly Polynomial Minimum Cost Circulation Algorithm”
Éva Tardos · 1985
Earlier work this paper cites.
“Solving minimum-cost flow problems by successive approximation”
Andrew Goldberg and Robert Tarjan · 1987
Earlier work this paper cites.
“A computational comparison of the Dinic and network simplex methods for maximum flow”
Donald Goldfarb and Michael Grigoriadis · 1988
Earlier work this paper cites.
“An O ( n 2 ( m + n log n ) log n ) O(n^{2}(m+n\log n)\log n) Min-Cost Flow Algorithm”
Zvi Galil and Éva Tardos · 1988
Earlier work this paper cites.
“A new approach to the maximum-flow problem”
Andrew. Goldberg and Robert Tarjan · 1988
Earlier work this paper cites.
“A polynomial-time algorithm, based on Newton’s method, for linear programming”
James Renegar · 1988
Earlier work this paper cites.
“Faster Scaling Algorithms for Network Problems”
Harold. Gabow and Robert Tarjan · 1989
Earlier work this paper cites.
“Finding Minimum-Cost Circulations by Canceling Negative Cycles”
Andrew. Goldberg and Robert. Tarjan · 1989
Earlier work this paper cites.
“Finding minimum-cost flows by double scaling”
Ravindra. Ahuja, Andrew. Goldberg, James. Orlin and Robert Tarjan · 1992
Earlier work this paper cites.
“A Combinatorial Interior Point Method for Network Flow Problems”
C. Wallacher and U. Zimmermann · 1992
Earlier work this paper cites.
“Polynomial Dual Network Simplex Algorithms”
James. Orlin, Serge. Plotkin and Éva Tardos · 1993
Earlier work this paper cites.
“A Faster Strongly Polynomial Minimum Cost Flow Algorithm”
James. Orlin · 1993
Earlier work this paper cites.
“A graph-theoretic game and its application to the k-server problem”
Noga Alon, Richard Karp, David Peleg and Douglas West · 1995
Earlier work this paper cites.
“Scaling Algorithms for the Shortest Paths Problem”
Andrew. Goldberg · 1995
Earlier work this paper cites.
“A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows”
James. Orlin · 1996
Earlier work this paper cites.
“Beyond the Flow Decomposition Barrier” Announced at FOCS’97
Andrew. Goldberg and Satish Rao · 1998
Earlier work this paper cites.
“Introductory lectures on convex programming”, 1998
Yu Nesterov · 1998
Earlier work this paper cites.
“Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms”
Tom Leighton and Satish Rao · 1999
Earlier work this paper cites.
“Minimizing a Convex Cost Closure Set”
D.S. Hochbaum and M. Queyranne · 2003
Earlier work this paper cites.
“Solving sparse, symmetric, diagonally-dominant linear systems in time O ( m 1.31 ) O(m^{1.31}) ”
Daniel Spielman and Shang-Hua Teng · 2003
Earlier work this paper cites.
Yuri Boykov and Vladimir Kolmogorov · 2004
Earlier work this paper cites.
“Convex Optimization”
Stephen Boyd and Lieven Vandenberghe · 2004
Earlier work this paper cites.
“Interior point polynomial time methods in convex programming” Available at https://www2.isye.gatech.edu/~nemirovs/Lect_IPM.pdf
Arkadi Nemirovski · 2004
Earlier work this paper cites.
“Introductory Lectures on Convex Optimization - A Basic Course” Available at: https://wwwfr.uni.lu/content/download/92121/1121193/file/NesB.pdf 87
Yurii. Nesterov · 2004
Earlier work this paper cites.
Daniel. Spielman and Shang-Hua Teng · 2004
Cited alongside, same era.
“Faster Approximate Lossy Generalized Flow via Interior Point Algorithms”
Samuel. Daitch and Daniel. Spielman · 2008
Cited alongside, same era.
“The partial augment–relabel algorithm for the maximum flow problem”
Andrew Goldberg · 2008
Cited alongside, same era.
“The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem”
Dorit. Hochbaum · 2008
Cited alongside, same era.
“Optimal hierarchical decompositions for congestion minimization in networks”
Harald Räcke · 2008
Cited alongside, same era.
Thatchaphol Saranurak 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.
“Faster p-norm minimizing flows, via smoothed q-norm problems”
Deeksha Adil and Sushant Sachdeva · 2020
Later among the works it cites.
“Fully-dynamic graph sparsifiers against an adaptive adversary”
Aaron Bernstein, Jan Brand, Maximilian Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford and He Sun · 2020
Later among the works it cites.
“Deterministic decremental reachability, SCC, and shortest paths via directed expanders and congestion balancing”
Aaron Bernstein, Maximilian Gutenberg and Thatchaphol Saranurak · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
“A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem”
Bala Chandran and Dorit Hochbaum · 2009
Cited alongside, same era.
“Graph partitioning using single commodity flows”
Rohit Khandekar, Satish Rao and Umesh Vazirani · 2009
Cited alongside, same era.
Barak Fishbain, Dorit. Hochbaum and Stefan Muller · 2010
Cited alongside, same era.
“Cut-matching games on directed graphs”
Anand Louis · 2010
Cited alongside, same era.
“Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs”
Aleksander Mądry · 2010
Cited alongside, same era.
Paul Christiano, Jonathan. Kelner, Aleksander Mądry, Daniel. Spielman and Shang-Hua Teng · 2011
Cited alongside, same era.
Jonathan. Kelner, Gary. Miller and Richard Peng · 2012
Cited alongside, same era.
Later among the works it cites.
“Bipartite matching in nearly-linear time on moderately dense graphs”
Jan Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song and Di Wang · 2020
Later among the works it cites.
Jan Brand, Yin Lee, Aaron Sidford and Zhao Song · 2020
Later among the works it cites.
“Fast dynamic cuts, distances and effective resistances via vertex sparsifiers”
Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng and Thatchaphol Saranurak · 2020
Later among the works it cites.
“p-Norm Flow Diffusion for Local Graph Clustering”
Kimon Fountoulakis, Di Wang and Shenghao Yang · 2020
Later among the works it cites.
Monika Henzinger, Satish Rao and Di Wang · 2020
Later among the works it cites.
“Unit Capacity Maxflow in Almost O ( m 4 / 3 ) O(m^{4/3}) Time”
Tarun Kathuria, Yang. Liu and Aaron Sidford · 2020
Later among the works it cites.
“Deterministic Min-cut in Poly-logarithmic Max-flows”
Jason Li and Debmalya Panigrahi · 2020
Later among the works it cites.
“Faster energy maximization for faster maximum flow”
Yang Liu and Aaron Sidford · 2020
Later among the works it cites.
“Almost-Linear-Time Weighted ℓ p \ell_{p} -Norm Solvers in Slightly Dense Graphs via Sparsification”
Deeksha Adil, Brian Bullins, Rasmus Kyng and Sushant Sachdeva · 2021
Later among the works it cites.
“Gomory-Hu Tree in Subcubic Time” Available at: https://arxiv.org/abs/2111.04958
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak and Ohad Trabelsi · 2021
Later among the works it cites.
“Faster Sparse Minimum Cost Flow by Electrical Flow Localization”
Kyriakos Axiotis, Aleksander Mądry and Adrian Vladu · 2021
Later among the works it cites.
“Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers”
Jan Brand, Yu Gao, Arun Jambulapati, Yin Lee, Yang. Liu, Richard Peng and Aaron Sidford · 2021
Later among the works it cites.
“Deterministic decremental sssp and approximate min-cost flow in almost-linear time”
Aaron Bernstein, Maximilian Gutenberg and Thatchaphol Saranurak · 2021
Later among the works it cites.
“Minimum cost flows, MDPs, and ℓ 1 \ell_{1} -regression in nearly linear time for dense instances”
Jan Brand, Yin Lee, Yang. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song and Di Wang · 2021
Later among the works it cites.
“The entropic barrier is n n -self-concordant” Available at: https://arxiv.org/abs/2112.10947 , 2021
Sinho Chewi · 2021
Later among the works it cites.
Julia Chuzhoy · 2021
Later among the works it cites.
“Minimum Cuts in Directed Graphs via Partial Sparsification”
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud and Thatchaphol Saranurak · 2021
Later among the works it cites.
Li Chen, Richard Peng and Di Wang · 2021
Later among the works it cites.
“Deterministic algorithms for decremental shortest paths via layered core decomposition”
Julia Chuzhoy and Thatchaphol Saranurak · 2021
Later among the works it cites.
“A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path”
Sally Dong, Yin Lee and Guanghao Ye · 2021
Later among the works it cites.
Yu Gao, Yang Liu and Richard Peng · 2021
Later among the works it cites.
“Vertex Connectivity in Poly-Logarithmic Max-Flows” Available at https://arxiv.org/abs/2104.00104
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai · 2021
Later among the works it cites.
Jason Li and Debmalya Panigrahi · 2021
Later among the works it cites.
“Tutorial on the Robust Interior Point Method”
Yin Lee and Santosh Vempala · 2021
Later among the works it cites.
“Universal Barrier Is n -Self-Concordant” Available at: https://arxiv.org/abs/1809.03011
Yin Lee and Man-Chung Yue · 2021
Later among the works it cites.
“A fast maximum flow algorithm”
James Orlin and Xiao-yue Gong · 2021
Later among the works it cites.
“ ℓ p \ell_{p} Isotonic Regression Algorithms Using an ℓ 0 \ell_{0} Approach”
Quentin. Stout · 2021
Later among the works it cites.
“Gomory-Hu Trees in Quadratic Time” Available at: https://arxiv.org/abs/2112.01042
Tianyi Zhang · 2021
Later among the works it cites.
“Negative-Weight Single-Source Shortest Paths in Near-linear Time”
Aaron Bernstein, Danupon Nanongkai and Christian Wulff-Nilsen · 2022
Closest in time.
“Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time”
Sally Dong, Yu Gao, Gramoz Goranci, Yin Lee, Richard Peng, Sushant Sachdeva and Guanghao Ye · 2022
Closest in time.
“Optimal Vertex Connectivity Oracles”
Seth Pettie, Thatchaphol Saranurak and Longhui Yin · 2022
Closest in time.
“Fast algorithms for computational optimal transport and wasserstein barycenter”
Wenshuo Guo, Nhat Ho and Michael Jordan · 2097
Closest in time.