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

In this paper we present a new algorithm for solving linear programs that requires only tildeO(√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 tildeO(1) linear systems and additional nearly linear time computation. Our method improves upon the previous best iteration bound by factor of tildeOmega((m/rank(A))1/4) for methods with polynomial time computable iterations and by tildeOmega((m/rank(A))1/2) for methods which solve at most tildeO(1) linear systems in each iteration. Our method is parallelizable and amenable to linear algebraic techniques for accelerating the linear system solver. As such, up to polylogarithmic factors we either match or improve upon the best previous running times in both depth and work for different ratios of m and rank(A). Moreover, our method matches up to polylogarithmic factors a theoretical limit established by Nesterov and Nemirovski in 1994 regarding the use of a "universal barrier" for interior point methods, thereby resolving a long-standing open question regarding the running time of polynomial time interior point methods for linear programming.