Fetching the paper…
Reading the bibliography…
In this paper, we consider the following inverse maintenance problem: given $A \in \mathbb{R}^{n\times d}$ and a number of rounds $r$, we receive a $n\times n$ diagonal matrix $D^{(k)}$ at round $k$ and we wish to maintain an efficient linear system solver for $A^{T}D^{(k)}A$ under the assumption $D^{(k)}$ does not change too rapidly.
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · 1984
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.
Self-concordant functions and polynomial-time methods in convex programming
Yu Nesterov and Arkadi Nemirovskiy · 1989
Earlier work this paper cites.
Speeding-up linear programming using fast matrix multiplication
Pravin M Vaidya · 1989
Earlier work this paper cites.
Acceleration and parallelization of the path-following interior point method for a linearly constrained convex quadratic problem
Yu Nesterov and A Nemirovsky · 1991
Earlier work this paper cites.
Interior-point polynomial algorithms in convex programming
Yurii Nesterov and Arkadii Semenovich Nemirovskii · 1994
Earlier work this paper cites.
Speeding up karmarkar’s algorithm for multicommodity flows
Sanjiv Kapoor and Pravin M Vaidya · 1996
Earlier work this paper cites.
Rounding of polytopes in the real number model of computation
Leonid G Khachiyan · 1996
Earlier work this paper cites.
A new algorithm for minimizing convex functions over convex sets
Pravin M Vaidya · 1996
Earlier work this paper cites.
Approximating fractional multicommodity flow independent of the number of commodities
Lisa K Fleischer · 2000
Earlier work this paper cites.
Adaptive estimation of a quadratic functional by model selection
Béatrice Laurent and Pascal Massart · 2000
Earlier work this paper cites.
Combinatorial optimization: polyhedra and efficiency
Alexander Schrijver · 2003
Earlier work this paper cites.
Minimum-volume enclosing ellipsoids and core sets
Piyush Kumar and E Alper Yildirim · 2005
Cited alongside, same era.
Subspace sampling and relative-error matrix approximation: Column-based methods
Petros Drineas, Michael W Mahoney, and S Muthukrishnan · 2006
Cited alongside, same era.
Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization
László Lovász and Santosh Vempala · 2006
Cited alongside, same era.
Faster and simpler algorithms for multicommodity flow and other fractional packing problems
Naveen Garg and Jochen Koenemann · 2007
Cited alongside, same era.
Faster approximation schemes for fractional multicommodity flow problems
George Karakostas · 2008
Cited alongside, same era.
Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L Nguyên · 2012
Later among the works it cites.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Later among the works it cites.
Runtime guarantees for regression problems
Hui Han Chin, Aleksander Madry, Gary L Miller, and Richard Peng · 2013
Later among the works it cites.
Low rank approximation and regression in input sparsity time
Kenneth L Clarkson and David P Woodruff · 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.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Aleksander Madry · 2010
Cited alongside, same era.
Recent progress and open problems in algorithmic convex geometry
Santosh S Vempala · 2010
Cited alongside, same era.
Randomized algorithms for matrices and data
Michael W. Mahoney · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Random walks on polytopes and an affine interior point method for linear programming
Ravindran Kannan and Hariharan Narayanan · 2012
Cited alongside, same era.
Iterative row sampling
Mu Li, Gary L Miller, and Richard Peng · 2012
Cited alongside, same era.
Fast approximation of matrix coherence and statistical leverage
Michael W Mahoney, Petros Drineas, Malik Magdon-Ismail, and David P Woodruff · 2012
Cited alongside, same era.
Yin Tat Lee and Aaron Sidford · 2013
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 · 2014
Later among the works it cites.
Lp row sampling by lewis weights
Michael B Cohen and Richard Peng · 2014
Later among the works it cites.
Powers of tensors and fast matrix multiplication
François Le Gall · 2014
Later among the works it 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
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.
A faster cutting plane method and its implications for combinatorial and convex optimization
Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong · 2015
Closest in time.