{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:15Z","timestamp":1781077755536,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642208065","type":"print"},{"value":"9783642208072","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_16","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T09:58:49Z","timestamp":1308391129000},"page":"192-206","source":"Crossref","is-referenced-by-count":22,"title":["A Subexponential Lower Bound for Zadeh\u2019s Pivoting Rule for Solving Linear Programs and Games"],"prefix":"10.1007","author":[{"given":"Oliver","family":"Friedmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/BFb0121192","volume-title":"Polyhedral Combinatorics, Mathematical Programming Studies","author":"D. Avis","year":"1978","unstructured":"Avis, D., Chv\u00e1tal, V.: Notes on Bland\u2019s pivoting rule. In: Polyhedral Combinatorics, Mathematical Programming Studies, vol.\u00a08, pp. 24\u201334. Springer, Heidelberg (1978), http:\/\/dx.doi.org\/10.1007\/BFb0121192"},{"key":"16_CR2","volume-title":"Dynamic programming and optimal control","author":"D. Bertsekas","year":"2001","unstructured":"Bertsekas, D.: Dynamic programming and optimal control, 2nd edn. Athena Scientific, Singapore (2001)","edition":"2"},{"key":"16_CR3","first-page":"2","volume":"3","author":"G.S. Bhat","year":"1996","unstructured":"Bhat, G.S., Savage, C.D.: Balanced gray codes. Electronic Journal of Combinatorics\u00a03, 2\u20135 (1996)","journal-title":"Electronic Journal of Combinatorics"},{"issue":"2","key":"16_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0020-0190(95)00101-H","volume":"56","author":"A. Broder","year":"1995","unstructured":"Broder, A., Dyer, M., Frieze, A., Raghavan, P., Upfal, E.: The worst-case running time of the random simplex algorithm is exponential in the height. Inf. Process. Lett.\u00a056(2), 79\u201381 (1995)","journal-title":"Inf. Process. Lett."},{"key":"16_CR5","doi-asserted-by":"publisher","DOI":"10.1515\/9781400884179","volume-title":"Linear programming and extensions","author":"G. Dantzig","year":"1963","unstructured":"Dantzig, G.: Linear programming and extensions. Princeton University Press, Princeton (1963)"},{"key":"16_CR6","volume-title":"Finite state Markov decision processes","author":"C. Derman","year":"1972","unstructured":"Derman, C.: Finite state Markov decision processes. Academic Press, London (1972)"},{"issue":"3","key":"16_CR7","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/BF01582232","volume":"34","author":"Y. Fathi","year":"1986","unstructured":"Fathi, Y., Tovey, C.: Affirmative action algorithms. Math. Program.\u00a034(3), 292\u2013301 (1986)","journal-title":"Math. Program."},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-642-14162-1_46","volume-title":"Automata, Languages and Programming","author":"J. Fearnley","year":"2010","unstructured":"Fearnley, J.: Exponential lower bounds for policy iteration. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06199, pp. 551\u2013562. Springer, Heidelberg (2010)"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Friedmann, O.: An exponential lower bound for the parity game strategy improvement algorithm as we know it. In: Proc. of 24th LICS, pp. 145\u2013156 (2009)","DOI":"10.1109\/LICS.2009.27"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Friedmann, O.: An exponential lower bound for the latest deterministic strategy iteration algorithms. Selected Papers of the Conference \u201cLogic in Computer Science 2009\u201d (to appear) (2010), a preprint available from http:\/\/www.tcs.ifi.lmu.de\/~friedman","DOI":"10.2168\/LMCS-7(3:23)2011"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Friedmann, O., Hansen, T., Zwick, U.: A subexponential lower bound for the random facet algorithm for parity games. In: Proc. of 22nd SODA (2011) (to appear)","DOI":"10.1137\/1.9781611973082.19"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Friedmann, O., Hansen, T., Zwick, U.: Subexponential lower bounds for randomized pivoting rules for solving linear programs (2011), a preprint available from http:\/\/www.tcs.ifi.lmu.de\/~friedman","DOI":"10.1145\/1993636.1993675"},{"issue":"3","key":"16_CR13","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/PL00009827","volume":"18","author":"B. G\u00e4rtner","year":"1998","unstructured":"G\u00e4rtner, B., Henk, M., Ziegler, G.: Randomized simplex algorithms on Klee-Minty cubes. Combinatorica\u00a018(3), 349\u2013372 (1998), http:\/\/dx.doi.org\/10.1007\/PL00009827","journal-title":"Combinatorica"},{"issue":"4","key":"16_CR14","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1002\/rsa.10099","volume":"23","author":"B. G\u00e4rtner","year":"2003","unstructured":"G\u00e4rtner, B., Tschirschnitz, F., Welzl, E., Solymosi, J., Valtr, P.: One line and n points. Random Structures & Algorithms\u00a023(4), 453\u2013471 (2003), http:\/\/dx.doi.org\/10.1002\/rsa.10099","journal-title":"Random Structures & Algorithms"},{"issue":"4","key":"16_CR15","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0166-218X(79)90004-0","volume":"1","author":"D. Goldfarb","year":"1979","unstructured":"Goldfarb, D., Sit, W.: Worst case behavior of the steepest edge simplex method. Discrete Applied Mathematics\u00a01(4), 277\u2013285 (1979), http:\/\/www.sciencedirect.com\/science\/article\/B6TYW-45GVXJ1-2B\/2\/a7035da2cf84d35e9503c69f883c23f7","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Logics, and Infinite Games","year":"2002","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games. LNCS, vol.\u00a02500. Springer, Heidelberg (2002)"},{"key":"16_CR17","volume-title":"Dynamic programming and Markov processes","author":"R. Howard","year":"1960","unstructured":"Howard, R.: Dynamic programming and Markov processes. MIT Press, Cambridge (1960)"},{"issue":"4","key":"16_CR18","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(4), 367\u2013377 (1973), http:\/\/www.sciencedirect.com\/science\/article\/B6V00-45FSNXP-1H\/2\/0968f0b25d2d8a2e0e160a8a248d06de","journal-title":"Discrete Mathematics"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Kalai, G.: A subexponential randomized simplex algorithm (extended abstract). In: Proc. of 24th STOC. pp. 475\u2013482 (1992)","DOI":"10.1145\/129712.129759"},{"key":"16_CR20","first-page":"217","volume":"79","author":"G. Kalai","year":"1997","unstructured":"Kalai, G.: Linear programming, the simplex algorithm and simple polytopes. Mathematical Programming\u00a079, 217\u2013233 (1997)","journal-title":"Mathematical Programming"},{"key":"16_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":"4-5","key":"16_CR22","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J. Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica\u00a016(4-5), 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"16_CR23","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov decision processes","author":"M. Puterman","year":"1994","unstructured":"Puterman, M.: Markov decision processes. Wiley, Chichester (1994)"},{"key":"16_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/10722167_18","volume-title":"Computer Aided Verification","author":"J. V\u00f6ge","year":"2000","unstructured":"V\u00f6ge, J., Jurdzi\u0144ski, M.: A discrete strategy improvement algorithm for solving parity games (Extended abstract). In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol.\u00a01855, pp. 202\u2013215. Springer, Heidelberg (2000)"},{"key":"16_CR25","unstructured":"Zadeh, N.: What is the worst case behavior of the simplex algorithm? Tech. Rep.\u00a027, Department of Operations Research, Stanford (1980)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:16:12Z","timestamp":1560284172000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}