03869058

j

03869058 Adler, Ilan Megiddo, Nimrod Todd, Michael J. New results on the average behavior of simplex algorithms. Bull. Am. Math. Soc., New Ser. 11, 378-382 (1984). 1984 American Mathematical Society, Providence, RI EN average behavior performance of simplex algorithms

doi:10.1090/S0273-0979-1984-15317-5

Summary: 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\times 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.