Fetching the paper…
Reading the bibliography…
We present an algorithm that given a linear program with $n$ variables, $m$ constraints, and constraint matrix $A$, computes an $\epsilon$-approximate solution in $\tilde{O}(\sqrt{rank(A)}\log(1/\epsilon))$ iterations with high probability.
Extremum problems with inequalities as subsidiary conditions, studies and essays presented to r. courant on his 60th birthday, january 8, 1948, 187–204
Fritz John · 1948
Earlier work this paper cites.
Maximization of a linear function of variables subject to linear inequalities
George B Dantzig · 1951
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.
Finite dimensional subspaces of l { p } l_{\{}p\}
D. Lewis · 1978
Earlier work this paper cites.
Polynomial algorithms in linear programming
Leonid G Khachiyan · 1980
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · 1984
Earlier work this paper cites.
Parallel merge sort
Richard Cole · 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.
Approximation of zonoids by zonotopes
Jean Bourgain, Joram Lindenstrauss, and V Milman · 1989
Earlier work this paper cites.
Pathways to the optimal set in linear programming
Nimrod Megiddo · 1989
Earlier work this paper cites.
Self-concordant functions and polynomial-time methods in convex programming
Yu Nesterov and Arkadi Nemirovskiy · 1989
Earlier work this paper cites.
A new algorithm for minimizing convex functions over convex sets (extended abstract)
Pravin M. Vaidya · 1989
Earlier work this paper cites.
Speeding-up linear programming using fast matrix multiplication
Pravin M Vaidya · 1989
Earlier work this paper cites.
An algorithm for linear programming which requires o (((m+ n) n 2+(m+ n) 1.5 n) l) arithmetic operations
Pravin M Vaidya · 1990
Earlier work this paper cites.
Reducing the parallel complexity of certain linear programming problems (extended abstract)
Pravin M. Vaidya · 1990
Earlier work this paper cites.
Path-following methods for linear programming
Clovis C Gonzaga · 1992
Earlier work this paper cites.
Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem
RobertM. Freund · 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.
Interior-point polynomial algorithms in convex programming
Yurii Nesterov and Arkadii Semenovich Nemirovskii · 1994
Earlier work this paper cites.
Scaling, shifting and weighting in interior-point methods
Michael J Todd · 1994
Earlier work this paper cites.
Volumetric path following algorithms for linear programming
Kurt M. Anstreicher · 1996
Earlier work this paper cites.
Rounding of polytopes in the real number model of computation
Leonid G Khachiyan · 1996
Cited alongside, same era.
A new algorithm for minimizing convex functions over convex sets
Pravin M Vaidya · 1996
Cited alongside, same era.
A primal-dual interior point method whose running time depends only on the constraint matrix
Stephen A Vavasis and Yinyu Ye · 1996
Cited alongside, same era.
Self-scaled barriers and interior-point methods for convex programming
Yu E Nesterov and Michael J Todd · 1997
Cited alongside, same era.
Beyond the flow decomposition barrier
Andrew V. Goldberg and Satish Rao · 1998
Cited alongside, same era.
Introductory Lectures on Convex Optimization: A Basic Course
Yu Nesterov · 2003
Cited alongside, same era.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 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
Later among the works it cites.
Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
Yin Tat Lee and Aaron Sidford · 2013
Later among the works it cites.
Path finding i: Solving linear programs with \ \backslash ˜ o (sqrt(rank)) linear system solves
Yin Tat Lee and Aaron Sidford · 2013
Later among the works it cites.
Path finding ii: An \ \backslash ˜ o (m sqrt (n)) algorithm for the minimum cost flow problem
Yin Tat Lee and Aaron Sidford · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Combinatorial optimization: polyhedra and efficiency
Alexander Schrijver · 2003
Cited alongside, same era.
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.
The central path visits all the vertices of the klee–minty cube
Antoine Deza, Eissa Nematollahi, Reza Peyghami, and Tamás Terlaky · 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.
How good are interior point methods? klee–minty cubes tighten iteration-complexity bounds
Antoine Deza, Eissa Nematollahi, and Tamás Terlaky · 2008
Cited alongside, same era.
A redundant klee–minty construction with all the redundant constraints touching the feasible region
Eissa Nematollahi and Tamás Terlaky · 2008
Cited alongside, same era.
Navigating central path with electrical flows: from flows to matchings, and back
Aleksander Madry · 2013
Later among the works it cites.
A tight iteration-complexity upper bound for the mty predictor-corrector algorithm via redundant klee-minty cubes
Murat Mut and Tamás Terlaky · 2013
Later among the works it cites.
An efficient parallel solver for sdd linear systems
Richard Peng and Daniel A Spielman · 2013
Later among the works it cites.
Solving sdd linear systems in nearly m log 1/2 n time
Michael B Cohen, Rasmus Kyng, Gary L Miller, Jakub W Pachocki, Richard Peng, Anup B Rao, and Shen Chen Xu · 2014
Later among the works it cites.
Path-finding methods for linear programming : Solving linear programs in õ(sqrt(rank)) iterations and faster algorithms for maximum flow
Yin Tat Lee and Aaron Sidford · 2014
Later among the works it cites.
Sketching as a tool for numerical linear algebra
David P Woodruff et al · 2014
Later among the works it cites.
The entropic barrier: a simple and optimal universal self-concordant barrier
Sébastien Bubeck and Ronen Eldan · 2015
Later among the works it cites.
Uniform sampling for matrix approximation
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Later among the works it cites.
ℓ p \ell_{p} row sampling by lewis weights
Michael B. Cohen and Richard Peng · 2015
Later among the works it cites.
Sparsified cholesky solvers for sdd linear systems
Yin Tat Lee, Richard Peng, and Daniel A Spielman · 2015
Later among the works it cites.
Efficient inverse maintenance and faster algorithms for linear programming
Yin Tat Lee and Aaron Sidford · 2015
Later among the works it cites.
Faster convex optimization: Simulated annealing with an efficient universal barrier
Jacob Abernethy and Elad Hazan · 2016
Later among the works it cites.
Sparsified cholesky and multigrid solvers for connection laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman · 2016
Later among the works it cites.
Approximate gaussian elimination for laplacians-fast, sparse, and simple
Rasmus Kyng and Sushant Sachdeva · 2016
Later among the works it cites.
Solving linear programs in the current matrix multiplication time
Michael B. Cohen, Yin Tat Lee, and Zhao Song · 2018
Later among the works it cites.
Universal barrier is n n -self-concordant
Yin Tat Lee and Man-Chung Yue · 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
Closest in time.