{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:30Z","timestamp":1781077770237,"version":"3.54.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1986,6,1]],"date-time":"1986-06-01T00:00:00Z","timestamp":517968000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1986,6]]},"DOI":"10.1007\/bf01580646","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T04:55:46Z","timestamp":1114664146000},"page":"173-192","source":"Crossref","is-referenced-by-count":59,"title":["Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems"],"prefix":"10.1007","volume":"35","author":[{"given":"Michael J.","family":"Todd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The expected number of pivots needed to solve parametric linear programs and the efficiency of the self-dual simplex method","author":"I. Adler","year":"1983","unstructured":"I. Adler, \u201cThe expected number of pivots needed to solve parametric linear programs and the efficiency of the self-dual simplex method\u201d, manuscript, Department of Industrial Engineering and Operations Research, University of California, Berkeley, California (May 1983)."},{"key":"CR2","volume-title":"\u201cRandom linear programs\u201d, Operations Research Center Report No. 81-4","author":"I. Adler","year":"1981","unstructured":"I. Adler and S.E. Berenguer, \u201cRandom linear programs\u201d, Operations Research Center Report No. 81-4, University of California, Berkeley, California (1981)."},{"key":"CR3","volume-title":"A simplex-type algorithm solves linear programs of orderm \u00d7 n in only O((min(m, n))2) steps on the average","author":"I. Adler","year":"1983","unstructured":"I. Adler and N. Megiddo, \u201cA simplex-type algorithm solves linear programs of orderm \u00d7 n in only O((min(m, n))2) steps on the average\u201d, manuscript, Department of Industrial Engineering and Operations Research, University of California, Berkeley, and Department of Computer Science, Stanford University, Stanford, California (November 1983)."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"I. Adler and N. Megiddo, \u201cA simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension\u201d, in:Proceedings of the 16th annual ACM symposium on theory of computing (1984), pp. 312\u2013323.","DOI":"10.1145\/800057.808696"},{"key":"CR5","series-title":"Faculty Working Paper","volume-title":"Random linear programs with many variables and few constraints","author":"C. Blair","year":"1983","unstructured":"C. Blair, \u201cRandom linear programs with many variables and few constraints\u201d, Faculty Working Paper No. 946, College of Commerce and Business Administration, University of Illinois at Urbana-Champaign, Illinois (April 1983)."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1287\/moor.7.3.441","volume":"7","author":"K.H. Borgwardt","year":"1982","unstructured":"K.H. Borgwardt, \u201cSome distribution-independent results about the asymptotic order of the average number of steps of the simplex method\u201c,Mathematics of Operations Research 7 (1982) 441\u2013462.","journal-title":"Mathematics of Operations Research"},{"key":"CR7","first-page":"157","volume":"26","author":"K.H. Borgwardt","year":"1982","unstructured":"K.H. Borgwardt, \u201cThe average number of pivot steps required by the simplex-method is polynomial\u201c,Zeitschrift fur Operations Research 26 (1982) 157\u2013177.","journal-title":"Zeitschrift fur Operations Research"},{"key":"CR8","volume-title":"The simplex algorithm is very good! - On the expected number of pivot steps and related properties of random linear programs","author":"M. Haimovich","year":"1983","unstructured":"M. Haimovich, \u201cThe simplex algorithm is very good! - On the expected number of pivot steps and related properties of random linear programs\u201d, manuscript, Columbia University, New York, New York (April 1983)."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1287\/mnsc.11.7.681","volume":"11","author":"C.E. Lemke","year":"1965","unstructured":"C.E. Lemke, \u201cBimatrix equilibrium points and mathematical programming\u201c,Management Science 11 (1965) 681\u2013689.","journal-title":"Management Science"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF01585093","volume":"24","author":"J.H. May","year":"1982","unstructured":"J.H. May and R.L. Smith, \u201cRandom polytopes: their definition, generation, and aggregate properties\u201c,Mathematical Programming 24 (1982) 39\u201354.","journal-title":"Mathematical Programming"},{"key":"CR11","volume-title":"The probabilistic analysis of Lemke's algorithm for the linear complementarity problem","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, \u201cThe probabilistic analysis of Lemke's algorithm for the linear complementarity problem\u201d, manuscript, Department of Computer Science, Stanford University, Stanford, California (September 1983)."},{"key":"CR12","volume-title":"Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, \u201cImproved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm\u201d, manuscript, Department of Computer Science, Stanford University, Stanford, California (September 1983)."},{"key":"CR13","volume-title":"On the expected number of linear complementarity cones intersected by random and semi-random rays","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, \u201cOn the expected number of linear complementarity cones intersected by random and semi-random rays\u201d, manuscript, Department of Computer Science, Stanford University, Stanford, California (November 1983)."},{"key":"CR14","first-page":"607","volume-title":"Proceedings of the second symposium in linear programming","author":"T.S. Motzkin","year":"1955","unstructured":"T.S. Motzkin, \u201cThe probability of solvability of linear inequalities\u201c, 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\u2013611."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF02018666","volume":"2","author":"A. Prekopa","year":"1972","unstructured":"A. Prekopa, \u201cOn the number of vertices of random convex polyhedra\u201c,Periodica Mathematica Hungarica 2 (1972) 259\u2013282.","journal-title":"Periodica Mathematica Hungarica"},{"key":"CR16","volume-title":"On some average results for linear complementarity problems","author":"R. Saigal","year":"1983","unstructured":"R. Saigal, \u201cOn some average results for linear complementarity problems\u201d, manuscript, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois (August 1983)."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF02591902","volume":"27","author":"S. Smale","year":"1983","unstructured":"S. Smale, \u201cOn the average number of steps of the simplex method of linear programming\u201c,Mathematical Programming 27 (1983) 241\u2013262.","journal-title":"Mathematical Programming"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1007\/978-3-642-68874-4_20","volume-title":"Mathematical programming: the state of the art","author":"S. Smale","year":"1983","unstructured":"S. Smale, \u201cThe problem of the average speed of the simplex method\u201c, 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\u2013539."},{"key":"CR19","unstructured":"M.J. Todd, \u201cComplementarity in oriented matroids\u201d, to appear inSIAM Journal on Algebraic and Discrete Methods."},{"key":"CR20","volume-title":"\u201cLinear and quadratic programming in oriented matroids\u201d, Technical Report No. 565","author":"M.J. Todd","year":"1983","unstructured":"M.J. Todd, \u201cLinear and quadratic programming in oriented matroids\u201d, Technical Report No. 565, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York (March 1983)."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1007\/BF01581652","volume":"19","author":"L. Heyden Van der","year":"1980","unstructured":"L. Van der Heyden, \u201cA variable dimension algorithm for the linear complementarity problem\u201c,Mathematical Programming 19 (1980) 328\u2013346.","journal-title":"Mathematical Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01580646.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01580646\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01580646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T11:12:10Z","timestamp":1556881930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01580646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,6]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1986,6]]}},"alternative-id":["BF01580646"],"URL":"https:\/\/doi.org\/10.1007\/bf01580646","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,6]]}}}