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

We study the problem of solving linear program in the streaming model. Given a constraint matrix A∈ ℝm× n and vectors b∈ ℝm, c∈ ℝ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 widetilde O(√ nlog(1/ε)) passes and widetilde O(n2) space for an ε-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 widetilde O(√m) passes and widetilde O(n) space. In addition to our space-efficient IPM, we also give algorithms for solving SDD systems and isolation lemma in widetilde O(n) spaces, which are the cornerstones for our graph results.