Fetching the paper…
Reading the bibliography…
We present an $\tilde O(m+n^{1.5})$-time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g.
Solving empirical risk minimization in the current matrix multiplication time
Yin Tat Lee, Zhao Song, and Qiuyi Zhang · 1905
Earlier work this paper cites.
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak · 1910
Earlier work this paper cites.
Parallel approximate undirected shortest paths via low hop emulators
Alexandr Andoni, Clifford Stein, and Peilin Zhong · 1911
Earlier work this paper cites.
Matrixok kombinatorius tulajdonságairól (hungarian) on combinatorial properties of matrices
E. Egerváry · 1931
Earlier work this paper cites.
The hungarian method for the assignment problem
H. W Kuhn · 1955
Earlier work this paper cites.
Structure in Communication Nets
A. Shimbel · 1955
Earlier work this paper cites.
Paper P-923
R. Ford Network Flow Theory · 1956
Earlier work this paper cites.
Algorithms for the Assignment and Transportation Problems
J. Munkres · 1957
Earlier work this paper cites.
On a Routing Problem
R. Bellman · 1958
Earlier work this paper cites.
The Shortest Path Through a Maze
E. F. Moore · 1959
Earlier work this paper cites.
A new method for solving transportation-network problems
M. Iri · 1960
Earlier work this paper cites.
An Algorithm for the Solution of the Assignment Problem
E. A. Dinic and M. A. Kronrod · 1969
Earlier work this paper cites.
Algorithm for solution of a problem of maximum flow in networks with power estimation
Efim A Dinic · 1970
Earlier work this paper cites.
Theoretical improvements in algorithmic efficiency for network flow problems
Jack Edmonds and Richard M. Karp · 1972
Earlier work this paper cites.
Optimal Cycles in Graphs and the Minimal Cost-To-Time Ratio Problem
Eugene L. Lawler · 1972
Earlier work this paper cites.
An n 5 / 2 n^{5/2} algorithm for maximum matchings in bipartite graphs
John E. Hopcroft and Richard M. Karp · 1973
Earlier work this paper cites.
On finding maximum flows in networks with special structure and some applications
Alexander V Karzanov · 1973
Earlier work this paper cites.
Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication
Oscar H. Ibarra and Shlomo Moran · 1981
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 N. Gabow · 1985
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 N. Gabow and Robert Endre Tarjan · 1989
Earlier work this paper cites.
Speeding-up linear programming using fast matrix multiplication (extended abstract)
Pravin M. Vaidya · 1989
Earlier work this paper cites.
Faster scaling algorithms for general graph-matching problems
Harold N. Gabow and Robert Endre Tarjan · 1991
Earlier work this paper cites.
Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners
Pravin M. Vaidya · 1991
Earlier work this paper cites.
Scaling algorithms for the shortest paths problem
Andrew V. Goldberg · 1993
Earlier work this paper cites.
A technique for bounding the number of iterations in path following algorithms
Pravin M Vaidya and David S Atkinson · 1993
Earlier work this paper cites.
Volumetric path following algorithms for linear programming
Kurt M. Anstreicher · 1996
Earlier work this paper cites.
Self-scaled barriers and interior-point methods for convex programming
Yurii E. Nesterov and Michael J. Todd · 1997
Earlier work this paper cites.
A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees
M.-Y. Kao, T. W. Lam, W.-K. Sung, and H.-F. Ting · 1999
Earlier work this paper cites.
Randomness efficient identity testing of multivariate polynomials
Adam R Klivans and Daniel Spielman · 2001
Earlier work this paper cites.
Solving tall dense linear programs in nearly linear time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song · 2002
Earlier work this paper cites.
Polynomial value iteration algorithms for detrerminstic mdps
Omid Madani · 2002
Cited alongside, same era.
Circulation control for faster minimum cost flow in unit-capacity graphs
Kyriakos Axiotis, Aleksander Madry, and Adrian Vladu · 2003
Cited alongside, same era.
Combinatorial optimization: polyhedra and efficiency
Alexander Schrijver · 2003
Cited alongside, same era.
Solving sparse
Daniel A. Spielman and Shang-Hua Teng · 2003
Cited alongside, same era.
Maximum matchings via gaussian elimination
Marcin Mucha and Piotr Sankowski · 2004
Cited alongside, same era.
Dynamic transitive closure via dynamic matrix inverse (extended abstract)
Piotr Sankowski · 2004
Cited alongside, same era.
Approximate gaussian elimination for laplacians - fast, sparse, and simple
Rasmus Kyng and Sushant Sachdeva · 2016
Later among the works it cites.
Heavy hitters via cluster-preserving clustering
Kasper Green Larsen, Jelani Nelson, Huy L Nguyen, and Mikkel Thorup · 2016
Later among the works it cites.
Computing maximum flow with augmenting electrical flows
Aleksander Madry · 2016
Later among the works it cites.
Near-linear time approximation algorithms for optimal transport via sinkhorn iteration
Jason Altschuler, Jonathan Weed, and Philippe Rigollet · 2017
Later among the works it cites.
Negative-weight shortest paths and unit capacity minimum cost flow in O ( m 10 / 7 log W ) {O}(m^{10/7}\log{W}) time
Michael B Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 2004
Cited alongside, same era.
Algorithms – ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings
Piotr Sankowski · 2005
Cited alongside, same era.
Answering distance queries in directed graphs using fast matrix multiplication
Raphael Yuster and Uri Zwick · 2005
Cited alongside, same era.
Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I
Piotr Sankowski · 2006
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.
Maximum weight bipartite matching in matrix multiplication time
Piotr Sankowski · 2009
Cited alongside, same era.
Michael Kapralov · 2017
Later among the works it cites.
Dynamic spanning forest with worst-case update time: adaptive, las vegas, and O ( n 1 / 2 − ϵ ) {O}(n^{1/2-\epsilon}) -time
Danupon Nanongkai and Thatchaphol Saranurak · 2017
Later among the works it cites.
Dynamic minimum spanning forest with subpolynomial worst-case update time
Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen · 2017
Later among the works it cites.
Generalized preconditioning and undirected minimum-cost flow
Jonah Sherman · 2017
Later among the works it cites.
Fully-dynamic minimum spanning forest with improved worst-case update time
Christian Wulff-Nilsen · 2017
Later among the works it cites.
Towards optimal running times for optimal transport
Jose H. Blanchet, Arun Jambulapati, Carson Kent, and Aaron Sidford · 2018
Later among the works it cites.
Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions
Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang · 2018
Later among the works it cites.
Iterative refinement for ℓ p \ell_{p} -norm regression
Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva · 2019
Later among the works it cites.
Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds
Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak · 2019
Later among the works it cites.
Solving linear programs in the current matrix multiplication time
Michael B. Cohen, Yin Tat Lee, and Zhao Song · 2019
Later among the works it cites.
Flows in almost linear time via adaptive preconditioning
Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang · 2019
Later among the works it cites.
On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms
Tianyi Lin, Nhat Ho, and Michael I. Jordan · 2019
Later among the works it cites.
Solving linear programs with r a n k \sqrt{rank} linear system solves
Yin Tat Lee and Aaron Sidford · 2019
Later among the works it cites.
Stronger l 2 {}_{\mbox{2}} /l 2 {}_{\mbox{2}} compressed sensing; without iterating
Vasileios Nakos and Zhao Song · 2019
Later among the works it cites.
(nearly) sample-optimal sparse fourier transform in any dimension; ripless and filterless
Vasileios Nakos, Zhao Song, and Zhengyu Wang · 2019
Later among the works it cites.
Approximating optimal transport with linear programs
Kent Quanrud · 2019
Later among the works it cites.
Expander decomposition and pruning: Faster, stronger, and simpler
Thatchaphol Saranurak and Di Wang · 2019
Later among the works it cites.
Faster p p -norm minimizing flows, via smoothed q q -norm problems
Deeksha Adil and Sushant Sachdeva · 2020
Closest in time.
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
Closest in time.
Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing
Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak · 2020
Closest in time.
A deterministic linear program solver in current matrix multiplication time
Jan van den Brand · 2020
Closest in time.
The expander hierarchy and its applications to dynamic graph algorithms
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan · 2020
Closest in time.
Faster dynamic matrix inverse for faster lps
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang · 2020
Closest in time.
Faster parallel algorithm for approximate shortest path
Jason Li · 2020
Closest in time.
Faster divergence maximization for faster maximum flow
Yang P Liu and Aaron Sidford · 2020
Closest in time.
Faster energy maximization for faster maximum flow
Yang P Liu and Aaron Sidford · 2020
Closest in time.