3 ms·
Simplex uses solving systems of linear equations as a building block. Most variants of simplex have exponential runtime on worst case input. (But they do well
by eru 6y ago
Simplex uses solving systems of linear equations as a building block.
Most variants of simplex have exponential runtime on worst case input. (But they do well in practice.)
Recently, some variants of simplex with polynomial runtime have been found.
Solving linear equations was always known to 'only' take polynomial amounts of time at most. But the question is whether that's n^3 or n^2 or something better..