Solving linear programs in the current matrix multiplication time

By Michael B. Cohen, Yin Tat Lee, Zhao Song. Symposium on the Theory of Computing, 2018

376 citations recorded by the source corpus.

This paper shows how to solve linear programs of the form minAx=b,x≥0 c⊤x with n variables in time O*((nω+n2.5−α/2+n2+1/6) log(n/δ)) where ω is the exponent of matrix multiplication, α is the dual exponent of matrix multiplication, and δ is the relative accuracy. For the current value of ω∼2.37 and α∼0.31, our algorithm takes O*(nω log(n/δ)) time. When ω = 2, our algorithm takes O*(n2+1/6 log(n/δ)) time. Our algorithm utilizes several new concepts that we believe may be of independent interest: (1) We define a stochastic central path method. (2) We show how to maintain a projection matrix √W A⊤(AWA⊤)−1A √W in sub-quadratic time under ℓ2 multiplicative changes in the diagonal matrix W.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/dd68bb556b2f70a31dd2f8b089d270506e0cd3c5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Variance Reduction for Matrix Games (2019, background): “where the lower bound on is due to the best known theoretical runtimes of interior point methods: Õ(max{n,m}ω log(L/ )) [6] and Õ(nnz(A) + min{n,m}2) √ min{n,m} log(L/ )) [20], where ω is the (current) matrix multiplication exponent.”