Solving Linear Programs with Sqrt(rank) Linear System Solves

We present an algorithm that given a linear program with n variables, m constraints, and constraint matrix A, computes an ε-approximate solution in tildeO(√rank(A)log(1/ε)) iterations with high probability. Each iteration of our method consists of solving tildeO(1) linear systems and additional nearly linear time computation, improving by a factor of tildeOmega((m/rank(A))1/2) over the previous fastest method with this iteration cost due to Renegar (1988). Further, we provide a deterministic polynomial time computable tildeO(rank(A))-self-concordant barrier function for the polytope, resolving an open question of Nesterov and Nemirovski (1994) on the theory of "universal barriers" for interior point methods. Applying our techniques to the linear program formulation of maximum flow yields an tildeO(|E|√|V|log(U)) time algorithm for solving the maximum flow problem on directed graphs with |E| edges, |V| vertices, and integer capacities of size at most U. This improves upon the previous fastest polynomial running time of O(|E|min|E|1/2,|V|2/3log(|V|2/|E|)log(U)) achieved by Goldberg and Rao (1998). In the special case of solving dense directed unit capacity graphs our algorithm improves upon the previous fastest running times of O(|E|min|E|1/2,|V|2/3) achieved by Even and Tarjan (1975) and Karzanov (1973) and of tildeO(|E|10/7) achieved more recently by Mkadry (2013).