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).

[AM2] I. Adler and N. Megiddo, A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, Proc. 16th Annual ACM Sympos. on Theory of Computing, 1984, pp. 312323. 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 UrbanaChampaign, April 1983.

[Bo1] K.H. Borgwardt, Some distributionindependent results about the asymptotic order of the average number of pivot steps of the simplex method, Math. Oper. Res. 7 (1982), 441462. MR 667934

[Bo2] K.H. Borgwardt, The average number of steps required by the simplex method is polynomial, Z. Oper. Res. Ser. AB 26 (1982), 157177. 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. 159175. MR 332165

[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).

[Mu] K. G. Murty, Computational complexity of parametric linear progmmming, Math. Programming 19 (1980), 213219. MR 583280

[S1] S. Smale, On the average number of steps of the simplex method of linear programmming, Math. Programming 27 (1983), 241267. MR 725621

[S2] S. Smale, The problem of the average speed of the simplex method, Mathematical Programming: The State of the Art (A. Bachem, M. Grötschel and B. Korte, eds.), SpringerVerlag, 1983, pp. 530539. 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