Idioma:

Solving Linear Programs in the Current Matrix Multiplication Time

Cohen, Michael B. ; Lee, Yin Tat ; Song, Zhao

Journal of the ACM, 2021-02, Vol.68 (1), p.1-39 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Solving Linear Programs in the Current Matrix Multiplication Time
Autor: Cohen, Michael B. ; Lee, Yin Tat ; Song, Zhao
Assuntos: Algorithms ; Linear programming ; Mathematical analysis ; Matrix methods ; Multiplication
É parte de: Journal of the ACM, 2021-02, Vol.68 (1), p.1-39
Descrição: This article shows how to solve linear programs of the form min Ax = b , x ≥ 0 c ⊤ x with n variables in time O * (( n ω + n 2.5−α/2 + n 2+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 * ( n 2+1/6 log ( n /δ)) time. Our algorithm utilizes several new concepts that we believe may be of independent interest: • We define a stochastic central path method. • We show how to maintain a projection matrix √ W A ⊤ ( AWA ⊤ ) −1 A √ W in sub-quadratic time under \ell 2 multiplicative changes in the diagonal matrix W .
Editor: New York: Association for Computing Machinery
Idioma: Inglês

Voltar para lista de resultados