| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C05 | Linear programming |
| 68Q25 | Analysis of algorithms and problem complexity |
| 65K05 | Numerical mathematical programming methods |
| [1] | I. Adler, ”The expected number of pivots needed to solve parametric linear programs and the efficiency of the self-dual simplex method”, manuscript, Department of Industrial Engineering and Operations Research, University of California, Berkeley, California (May 1983). |
| [2] | I. Adler and S.E. Berenguer, ”Random linear programs”, Operations Research Center Report No. 81-4, University of California, Berkeley, California (1981). |
| [3] | I. Adler and N. Megiddo, ”A simplex-type algorithm solves linear programs of orderm {\(\times\)} n in only O((min(m, n))2) steps on the average”, manuscript, Department of Industrial Engineering and Operations Research, University of California, Berkeley, and Department of Computer Science, Stanford University, Stanford, California (November 1983). |
| [4] | I. Adler and N. Megiddo, ”A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension”, in:Proceedings of the 16th annual ACM symposium on theory of computing (1984), pp. 312–323. |
| [5] | C. Blair, ”Random linear programs with many variables and few constraints”, Faculty Working Paper No. 946, College of Commerce and Business Administration, University of Illinois at Urbana-Champaign, Illinois (April 1983). |
| [6] | K.H. Borgwardt, ”Some distribution-independent results about the asymptotic order of the average number of steps of the simplex method”,Mathematics of Operations Research 7 (1982) 441–462. ·Zbl 0498.90054 ·doi:10.1287/moor.7.3.441 |
| [7] | K.H. Borgwardt, ”The average number of pivot steps required by the simplex-method is polynomial”,Zeitschrift fur Operations Research 26 (1982) 157–177. ·Zbl 0488.90047 ·doi:10.1007/BF01917108 |
| [8] | M. Haimovich, ”The simplex algorithm is very good! - On the expected number of pivot steps and related properties of random linear programs”, manuscript, Columbia University, New York, New York (April 1983). |
| [9] | C.E. Lemke, ”Bimatrix equilibrium points and mathematical programming”,Management Science 11 (1965) 681–689. ·Zbl 0139.13103 ·doi:10.1287/mnsc.11.7.681 |
| [10] | J.H. May and R.L. Smith, ”Random polytopes: their definition, generation, and aggregate properties”,Mathematical Programming 24 (1982) 39–54. ·Zbl 0491.90060 ·doi:10.1007/BF01585093 |
| [11] | N. Megiddo, ”The probabilistic analysis of Lemke’s algorithm for the linear complementarity problem”, manuscript, Department of Computer Science, Stanford University, Stanford, California (September 1983). |
| [12] | N. Megiddo, ”Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm”, manuscript, Department of Computer Science, Stanford University, Stanford, California (September 1983). ·Zbl 0618.90061 |
| [13] | N. Megiddo, ”On the expected number of linear complementarity cones intersected by random and semi-random rays”, manuscript, Department of Computer Science, Stanford University, Stanford, California (November 1983). ·Zbl 0613.90092 |
| [14] | T.S. Motzkin, ”The probability of solvability of linear inequalities”, in: H.A. Antosiewicz, ed.,Proceedings of the second symposium in linear programming (National Bureau of Standards and Directorate of Management Analysis, USAF, 1955) pp. 607–611. |
| [15] | A. Prekopa, ”On the number of vertices of random convex polyhedra”,Periodica Mathematica Hungarica 2 (1972) 259–282. ·Zbl 0282.60007 ·doi:10.1007/BF02018666 |
| [16] | R. Saigal, ”On some average results for linear complementarity problems”, manuscript, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois (August 1983). |
| [17] | S. Smale, ”On the average number of steps of the simplex method of linear programming”,Mathematical Programming 27 (1983) 241–262. ·Zbl 0526.90060 ·doi:10.1007/BF02591902 |
| [18] | S. Smale, ”The problem of the average speed of the simplex method”, in: A. Bachem, M. Grotschel and B. Korte, eds.,Mathematical programming: the state of the art (Springer-Verlag, Berlin-Heidelberg-New York-Tokyo, 1983) pp. 530–539. ·Zbl 0552.90059 |
| [19] | M.J. Todd, ”Complementarity in oriented matroids”, to appear inSIAM Journal on Algebraic and Discrete Methods. ·Zbl 0556.05016 |
| [20] | M.J. Todd, ”Linear and quadratic programming in oriented matroids”, Technical Report No. 565, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York (March 1983). |
| [21] | L. Van der Heyden, ”A variable dimension algorithm for the linear complementarity problem”,Mathematical Programming 19 (1980) 328–346. ·Zbl 0442.90090 ·doi:10.1007/BF01581652 |
