Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching

Abstract

We study the problem of solving linear program in the streaming model. Given a constraint matrix $A\in {\mathbb{R}}^{m\times n}$ and vectors $b\in {\mathbb{R}}^m,c\in {\mathbb{R}}^n$, we develop a space-efficient interior point method that optimizes solely on the dual program. To this end, we obtain efficient algorithms for various different problems: * For general linear programs, we can solve them in $\tilde{O}(\sqrt{n}\log (1/\epsilon ))$ passes and $\tilde{O}(n^2)$ space for an $\epsilon$-approximate solution. To the best of our knowledge, this is the most efficient LP solver in streaming with no polynomial dependence on $m$ for both space and passes. * For bipartite graphs, we can solve the minimum vertex cover and maximum weight matching problem in $\tilde{O}(\sqrt{m})$ passes and $\tilde{O}(n)$ space. In addition to our space-efficient IPM, we also give algorithms for solving SDD systems and isolation lemma in $\tilde{O}(n)$ spaces, which are the cornerstones for our graph results.

72 pages, full version