{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T04:20:00Z","timestamp":1745986800633,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642360442"},{"type":"electronic","value":"9783642360466"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36046-6_6","type":"book-chapter","created":{"date-parts":[[2013,1,16]],"date-time":"2013-01-16T00:56:22Z","timestamp":1358297782000},"page":"53-56","source":"Crossref","is-referenced-by-count":0,"title":["Recent Results on Howard\u2019s Algorithm"],"prefix":"10.1007","author":[{"given":"Peter Bro","family":"Miltersen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1214\/aoms\/1177704593","volume":"33","author":"D. Blackwell","year":"1962","unstructured":"Blackwell, D.: Discrete dynamic programming. Ann. Math. Stat.\u00a033, 719\u2013726 (1962)","journal-title":"Ann. Math. Stat."},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., de Alfaro, L., Henzinger, T.A.: Strategy improvement for concurrent reachability games. In: Third International Conference on the Quantitative Evaluation of Systems, QEST 2006, pp. 291\u2013300. IEEE Computer Society (2006)","DOI":"10.1109\/QEST.2006.48"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"A. Condon","year":"1992","unstructured":"Condon, A.: The complexity of stochastic games. Information and Computation\u00a096, 203\u2013224 (1992)","journal-title":"Information and Computation"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/11787006_28","volume-title":"Automata, Languages and Programming","author":"K. Etessami","year":"2006","unstructured":"Etessami, K., Yannakakis, M.: Recursive Concurrent Stochastic Games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part II. LNCS, vol.\u00a04052, pp. 324\u2013335. Springer, Heidelberg (2006)"},{"key":"6_CR5","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, Part II. LNCS, vol.\u00a06199, pp. 551\u2013562. Springer, Heidelberg (2010)"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Friedmann, O.: An exponential lower bound for the parity game strategy improvement algorithm as we know it. In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, Los Angeles, CA, USA, August 11-14, pp. 145\u2013156 (2009)","DOI":"10.1109\/LICS.2009.27"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-20712-9_7","volume-title":"Computer Science \u2013 Theory and Applications","author":"K.A. Hansen","year":"2011","unstructured":"Hansen, K.A., Ibsen-Jensen, R., Miltersen, P.B.: The Complexity of Solving Reachability Games Using Value and Strategy Iteration. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 77\u201390. Springer, Heidelberg (2011)"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Hansen, K.A., Kouck\u00fd, M., Lauritzen, N., Miltersen, P.B., Tsigaridas, E.P.: Exact algorithms for solving stochastic games: extended abstract. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, June 6-8, pp. 205\u2013214. ACM (2011)","DOI":"10.1145\/1993636.1993665"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Hansen, K.A., Koucky, M., Miltersen, P.B.: Winning concurrent reachability games requires doubly exponential patience. In: 24th Annual IEEE Symposium on Logic in Computer Science (LICS 2009), pp. 332\u2013341. IEEE (2009)","DOI":"10.1109\/LICS.2009.44"},{"key":"6_CR10","first-page":"253","volume-title":"Innovations in Computer Science - ICS 2010","author":"T.D. Hansen","year":"2011","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. In: Innovations in Computer Science - ICS 2010, January 7-9, pp. 253\u2013263. Tsinghua University Press, Beijing (2011)"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/978-3-642-17517-6_37","volume-title":"Algorithms and Computation","author":"T.D. Hansen","year":"2010","unstructured":"Hansen, T.D., Zwick, U.: Lower Bounds for Howard\u2019s Algorithm for Finding Minimum Mean-Cost Cycles. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part I. LNCS, vol.\u00a06506, pp. 415\u2013426. Springer, Heidelberg (2010)"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Management Science, 359\u2013370 (1966)","DOI":"10.1287\/mnsc.12.5.359"},{"key":"6_CR13","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)"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1007\/978-3-642-33090-2_55","volume-title":"Algorithms \u2013 ESA 2012","author":"R. Ibsen-Jensen","year":"2012","unstructured":"Ibsen-Jensen, R., Miltersen, P.B.: Solving Simple Stochastic Games with Few Coin Toss Positions. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 636\u2013647. Springer, Heidelberg (2012)"},{"key":"6_CR15","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"M.L. Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York (1994)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Rao, S.S., Chandrasekaran, R., Nair, K.P.K.: Algorithms for discounted games. Journal of Optimization Theory and Applications, 627\u2013637 (1973)","DOI":"10.1007\/BF00935562"},{"key":"6_CR17","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. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol.\u00a01855, pp. 202\u2013215. Springer, Heidelberg (2000)"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Ye,Y.: The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate (2010), www.stanford.edu\/~yyye\/SimplexMDP4.pdf","DOI":"10.1287\/moor.1110.0516"}],"container-title":["Lecture Notes in Computer Science","Mathematical and Engineering Methods in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36046-6_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T17:16:37Z","timestamp":1745946997000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36046-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642360442","9783642360466"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36046-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}