Bulletin of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

New results on the average behavior of simplex algorithms

Author(s): Ilan Adler; Nimrod Megiddo; Michael J. Todd
Journal: Bull. Amer. Math. Soc. 11 (1984), 378-382.
MSC (1980): Primary 68C25; Secondary 90C05
MathSciNet review: 752803
Retrieve article in: PDF

References:

[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 (m², d²)) 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))²) 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. 312-323. 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.

[Bo1] K.-H. 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), 441-462. MR 667934

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

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

[S1] S. Smale, On the average number of steps of the simplex method of linear programmming, Math. Programming 27 (1983), 241-267. 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.), Springer-Verlag, 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.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|