{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T17:04:29Z","timestamp":1725728669132},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642390524"},{"type":"electronic","value":"9783642390531"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39053-1_29","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T00:28:12Z","timestamp":1370219292000},"page":"252-262","source":"Crossref","is-referenced-by-count":2,"title":["The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games"],"prefix":"10.1007","author":[{"given":"Thomas Dueholm","family":"Hansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Ibsen-Jensen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-642-10631-6_13","volume-title":"Algorithms and Computation","author":"D. Andersson","year":"2009","unstructured":"Andersson, D., Miltersen, P.B.: The complexity of solving stochastic games on graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 112\u2013121. Springer, Heidelberg (2009)"},{"key":"29_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-01513-7_9","volume-title":"Advances in Neural Networks \u2013 ISNN 2009","author":"H. Chen","year":"2009","unstructured":"Chen, H., Zhang, M., Zhao, Y.: A class of new large-update primal-dual interior-point algorithms for \n                  \n                    \n                  \n                  $\\emph{P}_\\ast(\\kappa)$\n                 linear complementarity problems. In: Yu, W., He, H., Zhang, N. (eds.) ISNN 2009, Part III. LNCS, vol.\u00a05553, pp. 77\u201387. Springer, Heidelberg (2009)"},{"key":"29_CR3","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.cam.2007.05.007","volume":"216","author":"G.-M. Cho","year":"2008","unstructured":"Cho, G.-M.: A new large-update interior point algorithm for P\n                *(\u03ba) linear complementarity problems. Journal of Computational and Applied Mathematics\u00a0216, 265\u2013278 (2008)","journal-title":"Journal of Computational and Applied Mathematics"},{"key":"29_CR4","volume-title":"Computer Science and Scientific Computing","author":"R.W. Cottle","year":"1992","unstructured":"Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. In: Computer Science and Scientific Computing. Academic Press, Boston (1992)"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer (1997)","DOI":"10.1007\/978-1-4612-4054-9"},{"key":"29_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/11537311_19","volume-title":"Fundamentals of Computation Theory","author":"B. G\u00e4rtner","year":"2005","unstructured":"G\u00e4rtner, B., R\u00fcst, L.: Simple stochastic games and P-matrix generalized linear complementarity problems. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 209\u2013220. Springer, Heidelberg (2005)"},{"key":"29_CR7","unstructured":"Hansen, T.D.: Worst-case Analysis of Strategy Iteration and the Simplex Method. PhD thesis, Aarhus University (2012)"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Hansen, T.D., Ibsen-Jensen, R.: The complexity of interior point methods for solving discounted turn-based stochastic games (2013), \n                  \n                    http:\/\/www.cs.au.dk\/~tdh\/papers\/bounding_kappa.pdf","DOI":"10.1007\/978-3-642-39053-1_29"},{"key":"29_CR9","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: Proc. of 2nd ICS, pp. 253\u2013263 (2011)"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10898-008-9348-0","volume":"47","author":"T. Ill\u00e9s","year":"2010","unstructured":"Ill\u00e9s, T., Nagy, M., Terlaky, T.: A polynomial path-following interior point algorithm for general linear complementarity problems. Journal of Global Optimization\u00a047, 329\u2013342 (2010)","journal-title":"Journal of Global Optimization"},{"key":"29_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-540-69407-6_32","volume-title":"Logic and Theory of Algorithms","author":"M. Jurdzi\u0144ski","year":"2008","unstructured":"Jurdzi\u0144ski, M., Savani, R.: A simple P-matrix linear complementarity problem for discounted games. In: Beckmann, A., Dimitracopoulos, C., L\u00f6we, B. (eds.) CiE 2008. LNCS, vol.\u00a05028, pp. 283\u2013293. Springer, Heidelberg (2008)"},{"issue":"4","key":"29_CR12","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica\u00a04(4), 373\u2013395 (1984)","journal-title":"Combinatorica"},{"issue":"5","key":"29_CR13","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0167-6377(91)90010-M","volume":"10","author":"M. Kojima","year":"1991","unstructured":"Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior point algorithms for linear complementarity problems: A summary. Oper. Res. Lett.\u00a010(5), 247\u2013254 (1991)","journal-title":"Oper. Res. Lett."},{"key":"29_CR14","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/BF01586054","volume":"54","author":"M. Kojima","year":"1992","unstructured":"Kojima, M., Megiddo, N., Ye, Y.: An interior point potential reduction algorithm for the linear complementarity problem. Mathematical Programming\u00a054, 54\u2013267 (1992)","journal-title":"Mathematical Programming"},{"key":"29_CR15","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s11081-011-9163-1","volume":"13","author":"N. Krishnamurthy","year":"2012","unstructured":"Krishnamurthy, N., Parthasarathy, T., Ravindran, G.: Solving subclasses of multi-player stochastic games via linear complementarity problem formulations \u2013 a survey and some new results. Optimization and Engineering\u00a013, 435\u2013457 (2012)","journal-title":"Optimization and Engineering"},{"key":"29_CR16","unstructured":"Littman, M.L.: Algorithms for sequential decision making. PhD thesis, Brown University (1996)"},{"key":"29_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-0189-2","volume-title":"Stochastic games and applications","author":"A. Neyman","year":"2003","unstructured":"Neyman, A., Sorin, S.: Stochastic games and applications. Kluwer Academic Publishers, Dordrecht (2003)"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/BF00935562","volume":"11","author":"S.S. Rao","year":"1973","unstructured":"Rao, S.S., Chandrasekaran, R., Nair, K.P.K.: Algorithms for discounted stochastic games. Journal of Optimization Theory and Applications\u00a011, 627\u2013637 (1973)","journal-title":"Journal of Optimization Theory and Applications"},{"key":"29_CR19","unstructured":"R\u00fcst, L.Y.: The P-matrix linear complementarity problem. PhD thesis, ETH Z\u00fcrich (2007)"},{"issue":"10","key":"29_CR20","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"L.S. Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Nat. Acad. Sci. U.S.A.\u00a039(10), 1095\u20131100 (1953)","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"key":"29_CR21","unstructured":"Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley-Interscience series in discrete mathematics and optimization. Wiley (1998)"}],"container-title":["Lecture Notes in Computer Science","The Nature of Computation. Logic, Algorithms, Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39053-1_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T12:18:14Z","timestamp":1557749894000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39053-1_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642390524","9783642390531"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39053-1_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}