What is the computational complexity of solving a linear program with $m$ constraints in $n$ variables?
2026-03-27 15:35:44.1774625744
On
What is the computational complexity of linear programming?
15.8k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
1
On
Brand's 2020 result derandomized the Cohen, Lee and Song result. Here is the link https://arxiv.org/pdf/1910.11957.pdf
The best possible (I believe) is by Michael Cohen, Yin Tat Lee, and Zhao Song: Solving linear program in the current matrix multiplication time. https://arxiv.org/abs/1810.07896 (STOC 2019) Hope this helps.