{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T18:12:08Z","timestamp":1761675128725},"reference-count":22,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[1987,12,1]],"date-time":"1987-12-01T00:00:00Z","timestamp":565315200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":9360,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Complexity"],"published-print":{"date-parts":[[1987,12]]},"DOI":"10.1016\/0885-064x(87)90007-0","type":"journal-article","created":{"date-parts":[[2004,11,6]],"date-time":"2004-11-06T13:01:23Z","timestamp":1099746083000},"page":"372-387","source":"Crossref","is-referenced-by-count":28,"title":["A simplex variant solving an m \u00d7 d linear program in O(min(m2, d2) expected number of pivot steps"],"prefix":"10.1016","volume":"3","author":[{"given":"Ilan","family":"Adler","sequence":"first","affiliation":[]},{"given":"Richard M","family":"Karp","sequence":"additional","affiliation":[]},{"given":"Ron","family":"Shamir","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0885-064X(87)90007-0_BIB1","series-title":"The Expected Number of Pivots Needed to Solve Parametric Linear Programs and the Efficiency of the Self-Dual Simplex Method","author":"Adler","year":"1983"},{"key":"10.1016\/0885-064X(87)90007-0_BIB2","series-title":"Operations Research Center Report No. 81-4","article-title":"Random Linear Programs","author":"Adler","year":"1981"},{"key":"10.1016\/0885-064X(87)90007-0_BIB3","series-title":"Generating random linear programs","author":"Adler","year":"1983"},{"issue":"No. 4","key":"10.1016\/0885-064X(87)90007-0_BIB4","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1287\/moor.11.4.570","article-title":"A family of simplex variants solving an m \u00d7 d linear program in expected number of pivots depending on d only","volume":"11","author":"Adler","year":"1986","journal-title":"Math. Oper. Res."},{"key":"10.1016\/0885-064X(87)90007-0_BIB5","series-title":"A simplex-type algorithm solves linear programs of order m \u00d7 n in only O((min(m, n))2) steps on the average, preliminary report","author":"Adler","year":"1983"},{"issue":"No. 4","key":"10.1016\/0885-064X(87)90007-0_BIB6","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1145\/4221.4222","article-title":"A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension","volume":"32","author":"Adler","year":"1985","journal-title":"J. Assoc. Comput. Mach."},{"issue":"No. 1","key":"10.1016\/0885-064X(87)90007-0_BIB7","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF01582163","article-title":"Random linear programs with many variables and few constraints","volume":"34","author":"Blair","year":"1986","journal-title":"Math. Programming"},{"issue":"No. 3","key":"10.1016\/0885-064X(87)90007-0_BIB8","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1287\/moor.7.3.441","article-title":"Some distribution-independent results about the asymptotic order of the average number of pivot steps of the simplex method","volume":"7","author":"Borgwardt","year":"1982","journal-title":"Math. Oper. Res."},{"key":"10.1016\/0885-064X(87)90007-0_BIB9","first-page":"157","article-title":"The average number of pivot steps required by the simplex-method is polynomial","volume":"26","author":"Borgwardt","year":"1982","journal-title":"Z. Oper. Res."},{"key":"10.1016\/0885-064X(87)90007-0_BIB10","series-title":"Linear Programming and Extensions","author":"Dantzig","year":"1963"},{"issue":"No. 1","key":"10.1016\/0885-064X(87)90007-0_BIB11","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1002\/nav.3800020106","article-title":"The computational algorithm for the parametric objective function","volume":"2","author":"Gass","year":"1955","journal-title":"Naval Res. Logist. Quart."},{"key":"10.1016\/0885-064X(87)90007-0_BIB12","series-title":"The simplex algorithm is very good!-On the expected number of pivot steps and related properties of random linear programs","author":"Haimovich","year":"1983"},{"key":"10.1016\/0885-064X(87)90007-0_BIB13","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0012-365X(73)90171-4","article-title":"The simplex algorithm with the pivot rule of maximizing improvement criterion","volume":"4","author":"Jeroslow","year":"1973","journal-title":"Discrete Math."},{"key":"10.1016\/0885-064X(87)90007-0_BIB14","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","article-title":"A new polynomial-time algorithm for linear programming","volume":"4","author":"Karmarkar","year":"1984","journal-title":"Combinatorica"},{"key":"10.1016\/0885-064X(87)90007-0_BIB15","series-title":"Proceedings, 3rd Symposium on Inequalities","first-page":"159","article-title":"How good is the simplex algorithm?","author":"Klee","year":"1972"},{"key":"10.1016\/0885-064X(87)90007-0_BIB16","series-title":"Proceedings, 15th Symposium in Applied Mathematics","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1090\/psapm\/015\/0161746","article-title":"An experimental study of the simplex method","author":"Kuhn","year":"1963"},{"key":"10.1016\/0885-064X(87)90007-0_BIB17","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF01585093","article-title":"Random polytopes: Their definition, generalization and aggregate properties","volume":"24","author":"May","year":"1982","journal-title":"Math. Programming"},{"key":"10.1016\/0885-064X(87)90007-0_BIB18","first-page":"271","article-title":"A note on the generality of the self-dual algorithm with various starting points","volume":"49","author":"Megiddo","year":"1985","journal-title":"Methods Oper. Res."},{"issue":"No. 2","key":"10.1016\/0885-064X(87)90007-0_BIB19","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/BF01580645","article-title":"Improved asymptotic analysis of the average number of steps performed by the self dual simplex algorithm","volume":"35","author":"Megiddo","year":"1986","journal-title":"Math. Programming"},{"key":"10.1016\/0885-064X(87)90007-0_BIB20","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF02591902","article-title":"On the average speed of the simplex method of linear programming","volume":"27","author":"Smale","year":"1983","journal-title":"Math. Programming"},{"key":"10.1016\/0885-064X(87)90007-0_BIB21","series-title":"Mathematical Programming: The State of the Art","first-page":"530","article-title":"The problem of the average speed of the simplex method","author":"Smale","year":"1983"},{"key":"10.1016\/0885-064X(87)90007-0_BIB22","article-title":"Polynomial Expected Behaviour of a Pivoting Algorithm for Linear Complementary and Linear Programming Problems","author":"Todd","year":"1983"}],"container-title":["Journal of Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0885064X87900070?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0885064X87900070?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,2]],"date-time":"2019-02-02T04:23:08Z","timestamp":1549081388000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0885064X87900070"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,12]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1987,12]]}},"alternative-id":["0885064X87900070"],"URL":"https:\/\/doi.org\/10.1016\/0885-064x(87)90007-0","relation":{},"ISSN":["0885-064X"],"issn-type":[{"value":"0885-064X","type":"print"}],"subject":[],"published":{"date-parts":[[1987,12]]}}}