New results on the average behavior of simplex algorithms
Ilan Adler, Nimrod Megiddo, Michael J. Todd · Bulletin of the American Mathematical Society · 1984
It has been a challenge for mathematicians to theoretically confirm the extremely good performance of simplex algorithms for linear programming.We have confirmed that a certain variant of the simplex method solves problems of order m X n in an expected number of steps which is bounded between two quadratic functions of the smaller dimension of the problem.Our probabilistic assumptions are rather weak.