论文标题
空间有效的内部方法，并应用于线性编程和最大重量双分匹配
Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
论文作者
论文摘要
我们研究了在流模型中求解线性程序的问题。给定一个约束矩阵$ a \ in \ mathbb {r}^{m \ times n} $和vectors $ b \ in \ mathbb {r}^m，in \ in \ mathbb {r}^n $，我们开发了一个在dual程序上优化的空间内点方法。为此，我们获得了各种不同问题的有效算法： *对于一般线性程序，我们可以将它们求解为$ \ widetilde o（\ sqrt n \ log（1/ε））$ passes和$ \ widetilde o（n^2）$ space $ε$ - approximate解决方案。据我们所知，这是流式传输中最有效的LP求解器，没有对空间和通行证的多项式依赖性。 *对于两部分图，我们可以在$ \ widetilde o（\ sqrt {m}）$ passes和$ \ widetilde o（n）$ space中解决最小顶点盖和最大重量匹配问题。 除了我们的太空效率IPM外，我们还提供了解决SDD系统和隔离引理$ \ widetilde o（n）$空间的算法，这是我们图形结果的基石。
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/ε))$ passes and $\widetilde O(n^2)$ 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(\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.
