2013

Path Finding I :Solving Linear Programs with \~O(sqrt(rank)) Linear System Solves

Lee, Yin Tat, Sidford, Aaron

Understand

In this paper we present a new algorithm for solving linear programs that requires only $\tilde{O}(\sqrt{rank(A)}L)$ iterations to solve a linear program with $m$ constraints, $n$ variables, and constraint matrix $A$, and bit complexity $L$.

Each iteration of our method consists of solving $\tilde{O}(1)$ linear systems and additional nearly linear time computation.
Our method improves upon the previous best iteration bound by factor of $\tilde{\Omega}((m/rank(A))^{1/4})$ for methods with polynomial time computable iterations and by $\tilde{\Omega}((m/rank(A))^{1/2})$ for methods which solve at most $\tilde{O}(1)$ linear systems in each iteration.
Our method is parallelizable and amenable to linear algebraic techniques for accelerating the linear system solver.

Built on

Maximization of a linear function of variables subject to linear inequalities
George B Dantzig · 1951
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.
The method of inscribed ellipsoids
LG Khachiyan, SP Tarasov, and II Erlikh · 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.
Pathways to the optimal set in linear programming
Nimrod Megiddo · 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.
Inverse problems and derivatives of determinants
Gilbert Strang · 1991
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.
On adaptive-step primal-dual interior-point algorithms for linear programming
Shinji Mizuno, Michael J Todd, and Yinyu Ye · 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.

Similar

Interior-point polynomial algorithms in convex programming
Yurii Nesterov and Arkadii Semenovich Nemirovskii · 1994
Cited alongside, same era.
Scaling, shifting and weighting in interior-point methods
Michael J Todd · 1994
Cited alongside, same era.
Volumetric path following algorithms for linear programming
Kurt M. Anstreicher · 1996
Cited alongside, same era.
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.
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.
Combinatorial optimization: algorithms and complexity
Christos H Papadimitriou and Kenneth Steiglitz · 1998
Cited alongside, same era.
Randomness efficient identity testing of multivariate polynomials
Adam R Klivans and Daniel Spielman · 2001
Cited alongside, same era.
Introductory Lectures on Convex Optimization: A Basic Course
Yu Nesterov · 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.
Simulated annealing in convex bodies and an o * {}^{\mbox{*}}
László Lovász and Santosh Vempala · 2006
Cited alongside, same era.

Then

A nearly-m log n time solver for sdd linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2011
Later among the works it cites.
Randomized algorithms for matrices and data
Michael W. Mahoney · 2011
Later among the works it cites.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Later among the works it cites.
Interior point algorithms: theory and analysis
Yinyu Ye · 2011
Later among the works it cites.
Iterative row sampling
Mu Li, Gary L Miller, and Richard Peng · 2012
Later among the works it cites.
Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings
Original
Jelani Nelson and Huy L Nguyên · 2012
Later among the works it cites.
Efficiency of coordinate descent methods on huge-scale optimization problems
Yu Nesterov · 2012
Later among the works it cites.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Later among the works it cites.
Low rank approximation and regression in input sparsity time
Kenneth L Clarkson and David P Woodruff · 2013
Closest in time.
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.
Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
Yin Tat Lee and Aaron Sidford · 2013
Closest in time.
Path finding ii: An \ \backslash ˜ o (m sqrt (n)) algorithm for the minimum cost flow problem
Original
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.
A tight iteration-complexity upper bound for the mty predictor-corrector algorithm via redundant klee-minty cubes
Murat Mut and Tamás Terlaky · 2013
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…