{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:40:19Z","timestamp":1771623619988,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642175169","type":"print"},{"value":"9783642175176","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-17517-6_37","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T20:13:41Z","timestamp":1291407221000},"page":"415-426","source":"Crossref","is-referenced-by-count":8,"title":["Lower Bounds for Howard\u2019s Algorithm for Finding Minimum Mean-Cost Cycles"],"prefix":"10.1007","author":[{"given":"Thomas Dueholm","family":"Hansen","sequence":"first","affiliation":[]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"37_CR1","volume-title":"Dynamic programming","author":"R.E. Bellman","year":"1957","unstructured":"Bellman, R.E.: Dynamic programming. Princeton University Press, Princeton (1957)"},{"key":"37_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R.E. Bellman","year":"1958","unstructured":"Bellman, R.E.: On a routing problem. Quarterly of Applied Mathematics\u00a016, 87\u201390 (1958)","journal-title":"Quarterly of Applied Mathematics"},{"issue":"4","key":"37_CR3","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/1027084.1027085","volume":"9","author":"A. Dasdan","year":"2004","unstructured":"Dasdan, A.: Experimental analysis of the fastest optimum cycle ratio and mean algorithms. ACM Trans. Des. Autom. Electron. Syst.\u00a09(4), 385\u2013418 (2004)","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"37_CR4","volume-title":"Finite state Markov decision processes","author":"C. Derman","year":"1972","unstructured":"Derman, C.: Finite state Markov decision processes. Academic Press, London (1972)"},{"key":"37_CR5","unstructured":"Fearnley, J.: Exponential lower bounds for policy iteration. In: Proc. of 37th ICALP (2010), Preliminaey version available at \n                    \n                      http:\/\/arxiv.org\/abs\/1003.3418v1"},{"key":"37_CR6","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford Jr.","year":"1956","unstructured":"Ford Jr., L.R., Fulkerson, D.R.: Maximal flow through a network. Canadian Journal of Mathematics\u00a08, 399\u2013404 (1956)","journal-title":"Canadian Journal of Mathematics"},{"key":"37_CR7","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":"37_CR8","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Goldberg, A.V., Tarjan, R.E., Werneck, R.F.F.: An experimental study of minimum mean cycle algorithms. In: Proc. of 11th ALENEX, pp. 1\u201313 (2009)","DOI":"10.1137\/1.9781611972894.1"},{"issue":"4","key":"37_CR9","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1145\/76359.76368","volume":"36","author":"A.V. Goldberg","year":"1989","unstructured":"Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM\u00a036(4), 873\u2013886 (1989)","journal-title":"Journal of the ACM"},{"key":"37_CR10","unstructured":"Hansen, T.D., Miltersen, P.B., Zwick, U.: Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. CoRR, abs\/1008.0530 (2010)"},{"key":"37_CR11","volume-title":"Dynamic programming and Markov processes","author":"R.A. Howard","year":"1960","unstructured":"Howard, R.A.: Dynamic programming and Markov processes. MIT Press, Cambridge (1960)"},{"issue":"3","key":"37_CR12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"R.M. Karp","year":"1978","unstructured":"Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Mathematics\u00a023(3), 309\u2013311 (1978)","journal-title":"Discrete Mathematics"},{"key":"37_CR13","unstructured":"Madani, O.: Personal communication (2008)"},{"issue":"4","key":"37_CR14","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N. Megiddo","year":"1979","unstructured":"Megiddo, N.: Combinatorial optimization with rational objective functions. Mathematics of Operations Research\u00a04(4), 414\u2013424 (1979)","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"37_CR15","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM\u00a030(4), 852\u2013865 (1983)","journal-title":"Journal of the ACM"},{"key":"37_CR16","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov decision processes","author":"M.L. Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov decision processes. Wiley, Chichester (1994)"},{"key":"37_CR17","unstructured":"Ye, Y.: The simplex method is strongly polynomial for the Markov decision problem with a fixed discount rate (2010), \n                    \n                      http:\/\/www.stanford.edu\/~yyye\/simplexmdp1.pdf"},{"key":"37_CR18","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230210206","volume":"21","author":"N.E. Young","year":"1991","unstructured":"Young, N.E., Tarjan, R.E., Orlin, J.B.: Faster parametric shortest path and minimum-balance algorithms. Networks\u00a021, 205\u2013221 (1991)","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17517-6_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T17:06:59Z","timestamp":1553274419000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17517-6_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175169","9783642175176"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17517-6_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}