Ellipsoid

空间高效的内点法，应用于线性规划和最大权重二分匹配

是计算机科学和运筹学中最基本的问题之一。在过去的半个世纪里，人们致力于开发时间高效的线性规划求解器，例如单纯形法 [23]、椭球法 [44] 和内点法 [41]。近几年，利用内点法 (IPM) 加速线性规划求解得到了深入研究 [20, 55, 13, 35, 65, 25, 71]。当 m ≈ n 时，最先进的 IPM 运行时间为 O(m2+1/18+mω)，当 m≫n 时，运行时间为 O(mn+n3)。为了实现这些令人印象深刻的改进，大多数此类算法利用随机和动态数据结构来同时维护原始解和对偶解。虽然这些算法在时间上是高效的，但它们不太可能以空间高效的方式实现：维护原始对偶公式需要 Ω(m + n2) 空间，当 m ≫ n 时尤其不能令人满意。在本文中，我们研究了在流式模型中求解线性规划的问题：在每一遍中，我们可以查询 A 的第 i 行和 b 的对应行。目标是设计一个既节省空间又节省遍历次数的 LP 求解器。所谓高效，我们的目标是获得一种不依赖于 m 的多项式的算法，或者更具体地说，我们提出一个健壮的 IPM 框架，该框架仅使用 e O(n2) 空间和 e O(√n log(1/ϵ)) 次遍历。1据我们所知，这是实现与 m 无关的空间和遍历最高效的流式 LP 算法。目前最好的 LP 流式算法要么需要 Ω(n) 次传递，要么需要 Ω(n2+m2) 空间来进行 O(√n) 次传递。对于高密集 LP（m≫n）的情况，我们的算法实现了最佳空间和传递。获得这些 LP 算法的关键因素是从时间高效的原始对偶 IPM 转变为时间效率较低的仅对偶 IPM [64]。从时间角度来看，仅对偶 IPM 需要 e O(√nlog(1/ϵ)) 次迭代，每次迭代可以在 e O(mn+poly(n)) 的时间内计算完成。然而，它比原始对偶方法更节省空间。具体而言，我们表明每次迭代，只需维护一个 n×n 的 Hessian 矩阵即可。为了获得 e O ( √ n log (1 /ϵ )) 次传递，我们证明了诸如 Lewis 权重 [ 56 , 21 ] 等非平凡量可以以仅使用 e O ( n 2 ) 空间的就地方式递归计算。既然我们有了用于流式模型中一般 LP 的空间和传递效率高的 IPM，我们将使用半流式模型中的图问题应用程序对其进行实例化。在半流式模型中，每条边及其权重都以在线方式显示，并且可能受到对抗顺序的影响，并且算法可以在 e O ( n ) 空间中对流进行多次传递。2我们特别关注最大权重二分匹配问题，其中带有权重的边以流式传输给我们，目标是找到一个匹配，使其中的总权重最大化。虽然对这个问题的研究已经很多（[ 2 , 36 , 24 , 3 , 9 ] 等），但大多数算法只能计算近似匹配，这意味着权重至少是最大权重的 (1 − ϵ )。对于精确匹配的情况，最近的一项研究 [ 6 ] 提供了一种算法，它取 n 4 / 3 + o (1)