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

S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, Tianyi Zhou

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 $\widetilde O(\sqrt n\log(1/\epsilon))$ passes and $\widetilde O(n^2)$ space for an $\epsilon$-approximate solution. To the best of our knowledge, this is the first LP solver in streaming that has no space dependence on $m$. * For linear programs with treewidth $\tau$, we can solve them in $\widetilde O(\sqrt{n}\tau\log(1/\epsilon))$ passes and $\widetilde O(n\tau)$ space for an $\epsilon$-approximate solution. * For bipartite graphs, we can solve the minimum vertex cover and maximum weight matching problem in $\widetilde O(\sqrt{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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment