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
MathSciNet review:
752803
Fulltext PDF
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
(87a:90085), http://dx.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 (84i:90079), http://dx.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
(84d:90064)

George
B. Dantzig, Linear programming and extensions, Princeton
University Press, Princeton, N.J., 1963. MR 0201189
(34 #1073)

[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
(48 #10492)

[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 (81k:90096), http://dx.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
(85f:90071), http://dx.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
(85d:90054)

[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.
 [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.
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
DOI:
http://dx.doi.org/10.1090/S027309791984153175
PII:
S 02730979(1984)153175
