A faster algorithm for solving general LPs

The fastest known LP solver for general (dense) linear programs is due to [Cohen, Lee and Song’19] and runs in O * ( n ω + n 2.5−α/2 + n 2+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 n 2+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 n 2+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 ω + n 2.5−α/2 + n 2+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 * ( n 2.055 ) time instead of O * ( n 2.16 ).

Authors

• Shunhua Jiang
• Zhao Song 0002
• Omri Weinstein
• Hengjie Zhang

Keywords

• Convex optimization
• Dynamic data-structure
• Linear programming