A faster algorithm for solving general LPs
A faster algorithm for solving general LPs
复制标题
DOI：
10.1145/3406325.3451058
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Shunhua Jiang;Zhao Song;Omri Weinstein;Hengjie Zhang
中科院分区：
文献类型：
--
作者：
Shunhua Jiang;Zhao Song;Omri Weinstein;Hengjie Zhang
对于一般（密集）线性规划，已知最快的LP求解器是[Cohen， Lee和Song ' 19]，运行时间为O*(nω +n2.5−α/2 +n2 +1/6)。随后的一些作品[Lee， Song and Zhang ' 19, Brand ' 20, Song and Yu ' 20]通过不同的技术获得了同样的复杂性，但它们都不能低于n2+1/6，即使ω=2。这使得求解线性系统的成本（nω）和求解线性规划的成本之间存在多项式差距，因此，改进n2+1/6项对于在这两个基本问题之间建立等效性至关重要。在本文中，我们将运行时间缩短到O*(nω +n2.5 - α/2 +n2 +1/18)，其中ω和α是快速矩阵乘法指数及其对偶。因此，在ω≈2和α≈1的一般信念下，我们的LP求解器运行时间为O*(n2.055)，而不是O*(n2.16)。
The fastest known LP solver for general (dense) linear programs is due to [Cohen, Lee and Song’19] and runs in O*(nω +n2.5−α/2 + n2+1/6) time. A number of follow-up works [Lee, Song and Zhang’19, Brand’20, Song and Yu’20] obtain the same complexity through different techniques, but none of them can go below n2+1/6, even if ω=2. This leaves a polynomial gap between the cost of solving linear systems (nω) and the cost of solving linear programs, and as such, improving the n2+1/6 term is crucial toward establishing an equivalence between these two fundamental problems. In this paper, we reduce the running time to O*(nω +n2.5−α/2 + n2+1/18) where ω and α are the fast matrix multiplication exponent and its dual. Hence, under the common belief that ω ≈ 2 and α ≈ 1, our LP solver runs in O*(n2.055) time instead of O*(n2.16).