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.

arXiv comment72 pages, full version

References in corpus (6)

• Sketching Cuts in Graphs and Hypergraphs
• Faster Dynamic Matrix Inverse for Faster LPs
• Faster Divergence Maximization for Faster Maximum Flow
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
• Faster Spectral Sparsification in Dynamic Streams

Cited by in corpus (3)

• Minimum Cost Flows, MDPs, and ${\ell }_1$-Regression in Nearly Linear Time for Dense Instances
• Generalized Leverage Score Sampling for Neural Networks
• A Two-Pass Lower Bound for Semi-Streaming Maximum Matching