{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T07:20:09Z","timestamp":1790666409559,"version":"4.1.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319075563","type":"print"},{"value":"9783319075570","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07557-0_2","type":"book-chapter","created":{"date-parts":[[2014,5,17]],"date-time":"2014-05-17T07:50:30Z","timestamp":1400313030000},"page":"13-24","source":"Crossref","is-referenced-by-count":14,"title":["On Simplex Pivoting Rules and Complexity Theory"],"prefix":"10.1007","author":[{"given":"Ilan","family":"Adler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aviad","family":"Rubinstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"4","key":"2_CR1","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1287\/moor.11.4.570","volume":"11","author":"I. Adler","year":"1986","unstructured":"Adler, I., Karp, R.M., Shamir, R.: A Family of Simplex Variants Solving an m x d Linear Program in Expected Number of Pivot Steps Depending on d Only. Mathematics of Operations Research\u00a011(4), 570\u2013590 (1986)","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"2_CR2","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1145\/4221.4222","volume":"32","author":"I. Adler","year":"1985","unstructured":"Adler, I., Megiddo, N.: A Simplex Algorithm whose Average Number of Steps is Bounded between Two Quadratic Functions of the Smaller Dimension. Journal of the ACM\u00a032(4), 471\u2013495 (1985)","journal-title":"Journal of the ACM"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Amenta, N., Ziegler, G.: Deformed products and maximal shadows of polytopes. In: Advances in Discrete and Computational Geometry, pp. 57\u201390 (1996)","DOI":"10.1090\/conm\/223\/03132"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/BFb0121192","volume":"8","author":"D. Avis","year":"1978","unstructured":"Avis, D., Chvatal, C.: Notes on Bland\u2019s Pivoting Rule. Math. Programming Study\u00a08, 24\u201334 (1978)","journal-title":"Math. Programming Study"},{"issue":"1","key":"2_CR5","first-page":"157","volume":"26","author":"K.H. Borgwardt","year":"1982","unstructured":"Borgwardt, K.H.: The Average Number of Steps Required by the Simplex Method is Polynomial. Zeitschrift fur Operations Research\u00a026(1), 157\u2013177 (1982)","journal-title":"Zeitschrift fur Operations Research"},{"issue":"2","key":"2_CR6","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-011-0445-3","volume":"134","author":"S. Chubanov","year":"2012","unstructured":"Chubanov, S.: A strongly polynomial algorithm for linear systems having a binary solution. Math. Programming\u00a0134(2), 533\u2013570 (2012)","journal-title":"Math. Programming"},{"key":"2_CR7","unstructured":"Cottle, R., Pang, J.-S., Stone, R.E.: The linear complementarity problem. Academic Press (1992)"},{"key":"#cr-split#-2_CR8.1","unstructured":"Dantzig, G.B.: Maximization of a Linear Function of Variables subject to Linear Inequalities (1947)"},{"key":"#cr-split#-2_CR8.2","unstructured":"Published in Koopmans, T.C. (ed.): Activity Analysis of Production and Allocation, pp. 339-347. Wiley & Chapman-Hall (1951)"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press and the RAND Corporation (1963)","DOI":"10.7249\/R366"},{"key":"2_CR10","unstructured":"Danzig, G.B., Ford, L.R., Fulkerson, D.R.: A Primal-Dual Algorithm for Linear Programming. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems, pp. 171\u2013181. Princeton University Press (1954)"},{"issue":"2","key":"2_CR11","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM\u00a019(2), 248\u2013264 (1972)","journal-title":"Journal of the ACM"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0377-2217(91)90343-T","volume":"52","author":"K. Fukuda","year":"1991","unstructured":"Fukuda, K., Matsui, T.: On the Finiteness of the Criss-cross Method. European Journal of Operations Research\u00a052, 119\u2013124 (1991)","journal-title":"European Journal of Operations Research"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Papadimitriou, C.H., Savani, R.: The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. ACM Transactions on Economics and Computation\u00a01(2), Article 9 (2013)","DOI":"10.1145\/2465769.2465774"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF01593804","volume":"12","author":"D. Goldfarb","year":"1977","unstructured":"Goldfarb, D., Reid, J.K.: A Practical Steepest-Edge Simplex Algorithm. Mathematical Programming\u00a012, 361\u2013371 (1977)","journal-title":"Mathematical Programming"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0012-365X(73)90171-4","volume":"4","author":"R.G. Jeroslow","year":"1973","unstructured":"Jeroslow, R.G.: The Simplex Algorithm with the Pivot Rule of Maximizing Criterion Improvement. Discrete Mathematics\u00a04, 367\u2013377 (1973)","journal-title":"Discrete Mathematics"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Kalai, G.: A Subexponential Randomized Simplex Algorithm. In: ACM 24th Symposium on Theory of Computing, pp. 475\u2013482 (1992)","DOI":"10.1145\/129712.129759"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1090\/S0273-0979-1992-00285-9","volume":"26","author":"G. Kalai","year":"1992","unstructured":"Kalai, G., Kleitman, D.: Quasi-polynomial Bounds for the Diameter of Graphs and Polyhedra. Bull. Amer. Math. Soc.\u00a026, 315\u2013316 (1992)","journal-title":"Bull. Amer. Math. Soc."},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N.K. Karmarkar","year":"1984","unstructured":"Karmarkar, N.K.: A New Polynomial-time Algorithm for Linear Programming. Combinatorica\u00a04, 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"2_CR20","unstructured":"Khachian, R.M.: A Polynomial Algorithm in Linear Programming. Doklady Akad. Nauk SSSR\u00a0244(5), 1093\u20131096; Translated in Soviet Math. Doklady, 20, 191\u2013194 (1979)"},{"key":"2_CR21","first-page":"159","volume-title":"Inequalities III","author":"V. Klee","year":"1972","unstructured":"Klee, V., Minty, G.J.: How Good is the Simplex Algorithm? In: Shisha, O. (ed.) Inequalities III, pp. 159\u2013175. Academic Press, New York (1972)"},{"issue":"2","key":"2_CR22","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C.E. Lemke","year":"1996","unstructured":"Lemke, C.E., Howson, J.T.: Equilibrium points of bimatrix games. SIAM Journal on Applied Mathematics\u00a012(2), 413\u2013423 (1996)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"4-5","key":"2_CR23","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J. Matousek","year":"1996","unstructured":"Matousek, J., Sharir, M., Welzl, E.: A Subexponential Bound for Linear programming. Algorithmica\u00a016(4-5), 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/BF01581642","volume":"19","author":"K.G. Murty","year":"1980","unstructured":"Murty, K.G.: Computational Complexity of Parametric Linear Programming. Mathematical Programming\u00a019, 213\u2013219 (1980)","journal-title":"Mathematical Programming"},{"key":"2_CR25","unstructured":"Papadimitriou, C.: Computational Complexity. Addison Wesley (1994)"},{"key":"2_CR26","first-page":"78","volume":"46","author":"C. Ross","year":"1990","unstructured":"Ross, C.: An Exponential Example for Terlaky\u2019s Pivoting Rule for the Criss-cross Simplex Method. Mathematical Programming\u00a046, 78\u201394 (1990)","journal-title":"Mathematical Programming"},{"issue":"1","key":"2_CR27","doi-asserted-by":"publisher","first-page":"383","DOI":"10.4007\/annals.2012.176.1.7","volume":"176","author":"F. Santos","year":"2013","unstructured":"Santos, F.: A Counterexample to the Hirsch Conjecture. Annals of Mathematics\u00a0176(1), 383\u2013412 (2013)","journal-title":"Annals of Mathematics"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02591902","volume":"27","author":"S. Smale","year":"1983","unstructured":"Smale, S.: On the Average Number of Steps of the Simplex Method of Linear Programming. Mathematical Programming\u00a027, 241\u2013267 (1983)","journal-title":"Mathematical Programming"},{"issue":"3","key":"2_CR29","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. Journal of the ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"Journal of the ACM"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"Tardos, E.: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs. Operations Research\u00a034, 250\u2013256 (1986)","journal-title":"Operations Research"},{"issue":"2","key":"2_CR31","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1111\/j.1468-0262.2006.00667.x","volume":"74","author":"R. Savani","year":"2006","unstructured":"Savani, R., von Stengel, B.: Hard to Solve Bimatrix Games. Econometrica\u00a074(2), 397\u2013429 (2006)","journal-title":"Econometrica"},{"key":"2_CR32","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1080\/02331938508843067","volume":"16","author":"T. Terlaky","year":"1990","unstructured":"Terlaky, T.: A Convergent Criss-cross Method. Optimization\u00a016, 683\u2013690 (1990)","journal-title":"Optimization"},{"key":"2_CR33","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF01580646","volume":"35","author":"M.J. Todd","year":"1986","unstructured":"Todd, M.J.: Polynomial Expected Behvior of Pivoting Algorithm for Linear Complementarity and Linear Programming Problems. Mathematical Programming\u00a035, 173\u2013192 (1986)","journal-title":"Mathematical Programming"},{"issue":"4","key":"2_CR34","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1287\/moor.1110.0516","volume":"36","author":"Y. Ye","year":"2011","unstructured":"Ye, Y.: The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate. Mathematics of Operations Research\u00a036(4), 593\u2013603 (2011)","journal-title":"Mathematics of Operations Research"},{"key":"2_CR35","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1287\/mnsc.15.7.426","volume":"15","author":"S. Zionts","year":"1979","unstructured":"Zionts, S.: The Criss-cross Method for Solving Linear Programming Problems. Management Science\u00a015, 426\u2013445 (1979)","journal-title":"Management Science"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07557-0_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T17:14:30Z","timestamp":1558890870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07557-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319075563","9783319075570"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07557-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}