Solving Linear Programs in the Current Matrix Multiplication Time

This article shows how to solve linear programs of the form min(Ax=b,x) (>= 0) c(inverted perpendicular)x with n variables in time O*((n(omega) + n(2.5-alpha/2) + n(2+1/6)) log(n/delta)), where omega is the exponent of matrix multiplication, alpha is the dual exponent of matrix multiplication, and delta is the relative accuracy. For the current value of omega similar to 2.37 and alpha similar to 0.31, our algorithm takes O* (n(omega)log(n/delta)) time. When omega = 2, our algorithm takes O* (n(2+1/6) log(n/delta)) 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 root WA(inverted perpendicular) (AWA(inverted perpendicular))(-1)A root W in sub-quadratic time under l(2) multiplicative changes in the diagonal matrix W.

Automated summary

This article discusses algorithms for solving linear programming problems by utilizing concepts such as matrix multiplication exponents and dual exponents. It introduces a new stochastic central path method and demonstrates a method for maintaining a projection matrix when the diagonal matrix undergoes multiplicative changes.