Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



New results on the average behavior of simplex algorithms

Authors: Ilan Adler, Nimrod Megiddo and Michael J. Todd
Journal: Bull. Amer. Math. Soc. 11 (1984), 378-382
MSC (1980): Primary 68C25; Secondary 90C05
MathSciNet review: 752803
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [A] I. Adler, The expected number of pivots needed to solve parametric linear programs and the efficiency of the self-dual simplex method, Dept. Industrial Engineering and Operations Res., Univ. of California, Berkeley, June 1983.
  • [AKS] I. Adler, R. M. Karp and R. Shamir, A simplex variant solving an m × d linear program in O (min (m2, d2)) expected number of steps, Report UCB CSD 83/158, Computer Science Division, Univ. of California, Berkeley, December 1983.
  • [AM1] I. Adler and N. Megiddo, A simplex-type algorithm solves linear programming problems of order m × n in only O ((min (m, n))2) steps on the average, November 1983 (manuscript).
  • Ilan Adler and Nimrod Megiddo, A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, J. Assoc. Comput. Mach. 32 (1985), no. 4, 871–895. MR 810342,
  • [Bl] C. E. Blair, Random linear programs with many variables and few constraints, Faculty Working Paper No. 946, College of Commerce and Business Administration, Univ. of Illinois at Urbana-Champaign, April 1983.
  • Karl-Heinz Borgwardt, Some distribution-independent results about the asymptotic order of the average number of pivot steps of the simplex method, Math. Oper. Res. 7 (1982), no. 3, 441–462. MR 667934,
  • K.-H. Borgwardt, The average number of pivot steps required by the simplex-method is polynomial, Z. Oper. Res. Ser. A-B 26 (1982), no. 5, A157–A177 (English, with German summary). MR 686603
  • [D] G. B. Dantzig, Linear programming and extensions, Princeton Univ. Press, Princeton, N.J., 1963. MR 201189
  • [H] M. Haimovich, The simplex algorithm is very good!--On the expected number of pivot steps and related properties of random linear programs, Columbia Univ., New York, April 1983 (manuscript).
  • [KM] V. Klee and G. J. Minty, How good is the simplex algorithm?, Inequalities. III, Academic Press, 1972, pp. 159-175. MR 332165
  • [K] L. G. Khachian, A polynomial algorithm in linear programming, Soviet Math. Dokl. 20 (1979), 191-194.
  • [Me1] N. Megiddo, Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm, Dept. of Computer Science, Stanford Univ., September 1983 (preliminary report).
  • [Me2] N. Megiddo, A note on the generality of the self-dual algorithm with various starting points, Dept. of Computer Science, Stanford Univ., December 1983 (preliminary report).
  • Katta G. Murty, Computational complexity of parametric linear programming, Math. Programming 19 (1980), no. 2, 213–219. MR 583280,
  • Steve Smale, On the average number of steps of the simplex method of linear programming, Math. Programming 27 (1983), no. 3, 241–262. MR 725621,
  • S. Smale, The problem of the average speed of the simplex method, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 530–539. MR 717413
  • [T] M. J. Todd, Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programrning problems, Tech. Rep. No. 595, School of Operations Res. and Industrial Enginnering, Cornell Univ., 1983.

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1980): 68C25, 90C05

Retrieve articles in all journals with MSC (1980): 68C25, 90C05

Additional Information


American Mathematical Society