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), 378382
MSC (1980):
Primary 68C25; Secondary 90C05
DOI:
https://doi.org/10.1090/S027309791984153175
MathSciNet review:
752803
Fulltext PDF Free Access
References  Similar Articles  Additional Information

[A] I. Adler, The expected number of pivots needed to solve parametric linear programs and the efficiency of the selfdual 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 (m^{2}, d^{2})) 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 simplextype 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, https://doi.org/10.1145/4221.4222

[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 UrbanaChampaign, April 1983.
 KarlHeinz Borgwardt, Some distributionindependent 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, https://doi.org/10.1287/moor.7.3.441
 K.H. Borgwardt, The average number of pivot steps required by the simplexmethod is polynomial, Z. Oper. Res. Ser. AB 26 (1982), no. 5, A157–A177 (English, with German summary). MR 686603
 George B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963. MR 0201189

[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).
 Victor Klee and George J. Minty, How good is the simplex algorithm?, Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), Academic Press, New York, 1972, pp. 159–175. MR 0332165

[K] L. G. Khachian, A polynomial algorithm in linear programming, Soviet Math. Dokl. 20 (1979), 191194.

[Me1] N. Megiddo, Improved asymptotic analysis of the average number of steps performed by the selfdual simplex algorithm, Dept. of Computer Science, Stanford Univ., September 1983 (preliminary report).

[Me2] N. Megiddo, A note on the generality of the selfdual 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, https://doi.org/10.1007/BF01581642
 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, https://doi.org/10.1007/BF02591902
 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.
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
DOI:
https://doi.org/10.1090/S027309791984153175