{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:12:33Z","timestamp":1725541953626},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112652"},{"type":"electronic","value":"9783642112669"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11266-9_32","type":"book-chapter","created":{"date-parts":[[2009,12,7]],"date-time":"2009-12-07T14:04:58Z","timestamp":1260194698000},"page":"382-393","source":"Crossref","is-referenced-by-count":0,"title":["Linear Complementarity Algorithms for Infinite Games"],"prefix":"10.1007","author":[{"given":"John","family":"Fearnley","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Jurdzi\u0144ski","sequence":"additional","affiliation":[]},{"given":"Rahul","family":"Savani","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"32_CR1","doi-asserted-by":"publisher","first-page":"871","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), 871\u2013895 (1985)","journal-title":"Journal of the ACM"},{"issue":"2","key":"32_CR2","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/j.dam.2006.04.029","volume":"155","author":"H. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Vorobyov, S.: A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games. Discrete Applied Mathematics\u00a0155(2), 210\u2013229 (2007)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"32_CR3","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/BF00940344","volume":"60","author":"S.J. Chung","year":"1989","unstructured":"Chung, S.J.: NP-Completeness of the Linear Complementarity Problem. Journal of Optimization Theory and Applications\u00a060(3), 393\u2013399 (1989)","journal-title":"Journal of Optimization Theory and Applications"},{"key":"32_CR4","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Linear Programming. Freeman, New York (1983)"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Condon, A.: On Algorithms for Simple Stochastic Games. In: Advances in Computational Complexity Theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a013, pp. 51\u201373. American Mathematical Society (1993)","DOI":"10.1090\/dimacs\/013\/04"},{"key":"32_CR6","volume-title":"The Linear Complementarity Problem","author":"R.W. Cottle","year":"1992","unstructured":"Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, London (1992)"},{"key":"32_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/3-540-56922-7_32","volume-title":"Computer Aided Verification","author":"E.A. Emerson","year":"1993","unstructured":"Emerson, E.A., Jutla, C.S., Sistla, A.P.: On Model-Checking for Fragments of \u03bc-Calculus. In: Courcoubetis, C. (ed.) CAV 1993. LNCS, vol.\u00a0697, pp. 385\u2013396. Springer, Heidelberg (1993)"},{"key":"32_CR8","volume-title":"Competitive Markov Decision Processes","author":"J. Filar","year":"1997","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer, Heidelberg (1997)"},{"key":"32_CR9","volume-title":"Logic in Computer Science (LICS)","author":"O. Friedman","year":"2009","unstructured":"Friedman, O.: A Super-Polynomial Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know It. In: Logic in Computer Science (LICS). IEEE, Los Alamitos (to appear, 2009)"},{"key":"32_CR10","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":"32_CR11","first-page":"179","volume-title":"Contributions to the Theory of Games","author":"D. Gillette","year":"1957","unstructured":"Gillette, D.: Stochastic Games with Zero Stop Probabilities. In: Contributions to the Theory of Games, pp. 179\u2013187. Princeton University Press, Princeton (1957)"},{"key":"32_CR12","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. A Guide to Current Research. LNCS, vol.\u00a02500. Springer, Heidelberg (2002)"},{"issue":"3","key":"32_CR13","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdzi\u0144ski","year":"1998","unstructured":"Jurdzi\u0144ski, M.: Deciding the Winner in Parity Games Is in UP\u00a0\u2229\u00a0co-UP. Information Processing Letters\u00a068(3), 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"key":"32_CR14","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)"},{"key":"32_CR15","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1287\/ijoc.6.2.188","volume":"6","author":"M. Melekopoglou","year":"1994","unstructured":"Melekopoglou, M., Condon, A.: On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes. ORSA Journal on Computing\u00a06, 188\u2013192 (1994)","journal-title":"ORSA Journal on Computing"},{"key":"32_CR16","unstructured":"Puri, A.: Theory of Hybrid Systems and Discrete Event Systems. PhD Thesis, University of California, Berkeley (1995)"},{"issue":"10","key":"32_CR17","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. Proceedings of the National Academy of Sciences of the United States of America\u00a039(10), 1095\u20131100 (1953)","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"key":"32_CR18","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"CONCUR \u201995 Concurrency Theory","author":"C. Stirling","year":"1995","unstructured":"Stirling, C.: Local Model Checking Games (Extended abstract). In: Lee, I., Smolka, S.A. (eds.) CONCUR 1995. LNCS, vol.\u00a0962, pp. 1\u201311. Springer, Heidelberg (1995)"},{"key":"32_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-540-70881-0_35","volume-title":"Perspectives of Systems Informatics","author":"O. Svensson","year":"2007","unstructured":"Svensson, O., Vorobyov, S.: Linear Complementarity and P-Matrices for Stochastic Games. In: Virbitskaite, I., Voronkov, A. (eds.) PSI 2006. LNCS, vol.\u00a04378, pp. 409\u2013423. Springer, Heidelberg (2007)"},{"key":"32_CR20","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":"32_CR21","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U. Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.: The Complexity of Mean Payoff Games on Graphs. Theoretical Computer Science\u00a0158, 343\u2013359 (1996)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2010: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11266-9_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,10]],"date-time":"2019-03-10T23:02:47Z","timestamp":1552258967000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11266-9_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642112652","9783642112669"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11266-9_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}