{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T17:30:15Z","timestamp":1776965415831,"version":"3.51.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1983,10,1]],"date-time":"1983-10-01T00:00:00Z","timestamp":433814400000},"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":[[1983,10]]},"DOI":"10.1007\/bf02591902","type":"journal-article","created":{"date-parts":[[2007,3,29]],"date-time":"2007-03-29T15:37:51Z","timestamp":1175182671000},"page":"241-262","source":"Crossref","is-referenced-by-count":186,"title":["On the average number of steps of the simplex method of linear programming"],"prefix":"10.1007","volume":"27","author":[{"given":"Steve","family":"Smale","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02591902_CR1","series-title":"Technical Report ORC 81-4","volume-title":"Random linear programs","author":"I. Adler","year":"1981","unstructured":"I. Adler and S. Berenguer, \u201cRandom linear programs\u201d, Technical Report ORC 81-4, Operations Research Center, University of California (Berkeley, 1981)."},{"key":"BF02591902_CR2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1090\/S0002-9947-1943-0007627-9","volume":"53","author":"C. Allendoerfer","year":"1943","unstructured":"C. Allendoerfer and A. Weil, \u201cThe Gauss-Bonnet theorem for Riemannian polyhedra\u201d, Transactions of the American Mathematical Society 53 (1943) 101\u2013129.","journal-title":"Transactions of the American Mathematical Society"},{"key":"BF02591902_CR3","unstructured":"K.-H. Borgwardt, \u201cThe average number of steps required by the simplex method is polynomial\u201d, to appear in Zeitschrift f\u00fcr Operations Research."},{"key":"BF02591902_CR4","first-page":"115","volume-title":"Mathematics of the Decision Sciences, Part 1","author":"R.W. Cottle","year":"1968","unstructured":"R.W. Cottle and G.B. Dantzig, \u201cComplementary pivot theory of mathematical programming\u201d, in: G.B. Dantzig and A.F. Veinott, Jr., eds., Mathematics of the Decision Sciences, Part 1 (American Mathematical Society, Providence, RI, 1968) pp. 115\u2013136."},{"key":"BF02591902_CR5","volume-title":"Linear programming and extensions","author":"G.B. Dantzig","year":"1963","unstructured":"G.B. Dantzig, Linear programming and extensions (Princeton University Press, Princeton, NJ, 1963)."},{"key":"BF02591902_CR6","series-title":"Technical Report SOL 80-3","volume-title":"Expected number of steps of the simplex method for a linear program with a convexity constraint","author":"G.B. Dantzig","year":"1980","unstructured":"G.B. Dantzig, \u201cExpected number of steps of the simplex method for a linear program with a convexity constraint\u201d, Technical Report SOL 80-3, Systems Optimization Laboratory, Department of Operations Research, Stanford University (Stanford, CA, 1980)."},{"key":"BF02591902_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.1.1.1","volume":"1","author":"B.C. Eaves","year":"1976","unstructured":"B.C. Eaves and H. Scarf, \u201cThe solution of systems of piecewise linear equations\u201d, Mathematics of Operations Research 1 (1976) 1\u201327.","journal-title":"Mathematics of Operations Research"},{"key":"BF02591902_CR8","volume-title":"An introduction to probability theory and its applications","author":"W. Feller","year":"1957","unstructured":"W. Feller, An introduction to probability theory and its applications, 2nd ed., Vol. 1 (Wiley, New York, 1957).","edition":"2nd ed."},{"key":"BF02591902_CR9","volume-title":"Activity analysis of production and allocation","author":"D. Gale","year":"1951","unstructured":"D. Gale, H.W. Kuhn, and A.W. Tucker, \u201cLinear programming and the theory of games\u201d, in: T.C. Koopmans, ed., Activity analysis of production and allocation (Wiley, New York, 1951)."},{"key":"BF02591902_CR10","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1002\/cpa.3160320302","volume":"32","author":"M. Hirsch","year":"1979","unstructured":"M. Hirsch and S. Smale, \u201cOn algorithms for solvingf(x)=0\u201d, Communications on Pure and Applied Mathematics 32 (1979) 281\u2013312.","journal-title":"Communications on Pure and Applied Mathematics"},{"key":"BF02591902_CR11","series-title":"Cowles Foundation Discussion Paper","volume-title":"Linear complementarity and the degree of mappings","author":"R. Howe","year":"1980","unstructured":"R. Howe, \u201cLinear complementarity and the degree of mappings\u201d, Cowles Foundation Discussion Paper No. 452, Yale University (New Haven, CT, 1980)."},{"key":"BF02591902_CR12","first-page":"159","volume-title":"Inequalities III","author":"V. Klee","year":"1972","unstructured":"V. Klee and G. Minty, \u201cHow good is the simplex algorithm?\u201d, in: O. Shisha, ed., Inequalities III (Academic Press, New York, 1972) pp. 159\u2013175."},{"key":"BF02591902_CR13","unstructured":"T.M. Liebling, \u201cOn the number of iterations of the simplex method\u201d, in: R. Henn, H. K\u00fcnzi, and H. Schubert, eds., Operations Research Verfahren\/Methods of Operations Research XVII (1973) 248\u2013264."},{"key":"BF02591902_CR14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF03023055","volume":"2","author":"L. Lov\u00e1sz","year":"1980","unstructured":"L. Lov\u00e1sz, \u201cA new linear programming algorithm\u2014Better or worse than the simplex method?\u201d, The Mathematical Intelligencer 2 (1980) 141\u2013146.","journal-title":"The Mathematical Intelligencer"},{"key":"BF02591902_CR15","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF01585093","volume":"24","author":"J. May","year":"1982","unstructured":"J. May and R. Smith, \u201cRandom polytopes: Their definition, generation, and aggregate properties, Mathematical Programming 24 (1982) 39\u201354.","journal-title":"Mathematical Programming"},{"key":"BF02591902_CR16","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BFb0120782","volume":"7","author":"K.G. Murty","year":"1978","unstructured":"K.G. Murty, \u201cComputational complexity of complementary pivot methods\u201d, Mathematical Programming Study 7 (1978) 61\u201373.","journal-title":"Mathematical Programming Study"},{"key":"BF02591902_CR17","unstructured":"M. Shub and S. Smale, \u201cComputational complexity: On the geometry of polynomials and a theory of cost, Part I\u201d, preprint (1982)."},{"key":"BF02591902_CR18","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0304-4068(76)90019-7","volume":"3","author":"S. Smale","year":"1976","unstructured":"S. Smale, \u201cA convergent process of price adjustment and global Newton methods\u201d, Journal of Mathematical Economics 3 (1976) 107\u2013120.","journal-title":"Journal of Mathematical Economics"},{"key":"BF02591902_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1981-14858-8","volume":"4","author":"S. Smale","year":"1981","unstructured":"S. Smale, \u201cThe fundamental theorem of algebra and complexity theory\u201d, Bulletin of the American Mathematical Society 4 (1981) 1\u201336.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"BF02591902_CR20","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0167-6377(82)90047-5","volume":"1","author":"J. Traub","year":"1982","unstructured":"J. Traub and H. Wo\u017aniakowski, \u201cComplexity of linear programming\u201d, Operations Research Letters 1 (1982) 59\u201362.","journal-title":"Operations Research Letters"},{"key":"BF02591902_CR21","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1126\/science.208.4441.240-a","volume":"208","author":"P. Wolfe","year":"1980","unstructured":"P. Wolfe, \u201cThe ellipsoid algorithm\u201d (Letter to the Editor), Science 208 (1980) 240\u2013242.","journal-title":"Science"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02591902.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02591902\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02591902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T23:37:50Z","timestamp":1558395470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02591902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,10]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1983,10]]}},"alternative-id":["BF02591902"],"URL":"https:\/\/doi.org\/10.1007\/bf02591902","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,10]]}}}