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

S. Cliff Liu, Zhao Song, Hengjie Zhang +2

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$, w…