A faster algorithm for solving general LPs
Abstrak
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).
Topik & Kata Kunci
Penulis (4)
Shunhua Jiang
Zhao Song
Omri Weinstein
Hengjie Zhang
Akses Cepat
- Tahun Terbit
- 2021
- Bahasa
- en
- Total Sitasi
- 79×
- Sumber Database
- Semantic Scholar
- DOI
- 10.1145/3406325.3451058
- Akses
- Open Access ✓