{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:57:10Z","timestamp":1725512230228},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540708803"},{"type":"electronic","value":"9783540708810"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-70881-0_35","type":"book-chapter","created":{"date-parts":[[2007,8,3]],"date-time":"2007-08-03T16:07:32Z","timestamp":1186157252000},"page":"409-423","source":"Crossref","is-referenced-by-count":3,"title":["Linear Complementarity and P-Matrices for Stochastic Games"],"prefix":"10.1007","author":[{"given":"Ola","family":"Svensson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergei","family":"Vorobyov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"35_CR1","unstructured":"Andersson, D., Vorobyov, S.: Fast algorithms for monotonic discounted linear programs with two variables per inequality. Manuscript submitted to Theoretical Computer Science, July 2006. Preliminary version available as Isaac Newton Institute Preprint NI06019-LAA."},{"key":"35_CR2","unstructured":"Bj\u00f6rklund, H., et al.: Controlled linear programming: Boundedness and duality. TR DIMACS-2004-56, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ (2004)"},{"key":"35_CR3","unstructured":"Bj\u00f6rklund, H., et al.: The controlled linear programming problem. TR DIMACS-2004-41, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ (2004)"},{"key":"35_CR4","unstructured":"Bj\u00f6rklund, H., Svensson, O., Vorobyov, S.: Controlled linear programming for infinite games. TR DIMACS-2005-13, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ (2005)"},{"key":"35_CR5","unstructured":"Bj\u00f6rklund, H., Svensson, O., Vorobyov, S.: Linear complementarity algorithms for mean payoff games. TR DIMACS-2005-05, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ (2005)"},{"issue":"3","key":"35_CR6","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2005.07.041","volume":"349","author":"H. Bj\u00f6rklund","year":"2005","unstructured":"Bj\u00f6rklund, H., Vorobyov, S.: Combinatorial structure and randomized subexponential algorithms for infinite games. Theoretical Computer Science\u00a0349(3), 347\u2013360 (2005)","journal-title":"Theoretical Computer Science"},{"key":"35_CR7","unstructured":"Bj\u00f6rklund, H., Vorobyov, S.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Applied Mathematics, to appear (2006), Available from \n                    \n                      http:\/\/www.sciencedirect.com\/\n                    \n                    \n                   27 June, 2006"},{"key":"35_CR8","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":"35_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0021-9800(70)80010-2","volume":"8","author":"R.W. Cottle","year":"1970","unstructured":"Cottle, R.W., Dantzig, G.B.: A generalization of the linear complementarity problem. Journal of Combinatorial Theory\u00a08, 79\u201390 (1970)","journal-title":"Journal of Combinatorial Theory"},{"key":"35_CR10","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":"35_CR11","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF01582570","volume":"64","author":"G. Coxson","year":"1994","unstructured":"Coxson, G.: The P-matrix problem is coNP-complete. Mathematical Programming\u00a064, 173\u2013178 (1994)","journal-title":"Mathematical Programming"},{"key":"35_CR12","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1023\/A:1008224418676","volume":"11","author":"A.A. Ebiefung","year":"1997","unstructured":"Ebiefung, A.A., Kostreva, M.M.: The generalized linear complementarity problem: least element theory and Z-matrices. Journal of Global Optimization\u00a011, 151\u2013161 (1997)","journal-title":"Journal of Global Optimization"},{"key":"35_CR13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A. Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. International Journ. of Game Theory\u00a08, 109\u2013113 (1979)","journal-title":"International Journ. of Game Theory"},{"issue":"5","key":"35_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"V.A. Gurvich","year":"1988","unstructured":"Gurvich, V.A., Karzanov, A.V., Khachiyan, L.G.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. U.S.S.R. Computational Mathematics and Mathematical Physics\u00a028(5), 85\u201391 (1988)","journal-title":"U.S.S.R. Computational Mathematics and Mathematical Physics"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"Kalai, G.: A subexponential randomized simplex algorithm. In: 24th ACM STOC, pp. 475\u2013482 (1992)","DOI":"10.1145\/129712.129759"},{"key":"35_CR16","first-page":"217","volume":"79","author":"G. Kalai","year":"1997","unstructured":"Kalai, G.: Linear programming, the simplex algorithm and simple polytopes. Math. Prog (Ser. B)\u00a079, 217\u2013234 (1997)","journal-title":"Math. Prog. (Ser. B)"},{"key":"35_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-54509-3","volume-title":"A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems","author":"M. Kojima","year":"1991","unstructured":"Kojima, M., et al.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. LNCS, vol.\u00a0538. Springer, Heidelberg (1991)"},{"key":"35_CR18","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, M.: A subexponential bound for linear programming. Algorithmica\u00a016, 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"35_CR19","unstructured":"Megiddo, N.: A note on the complexity of P-matrix LCP and computing the equilibrium. Technical Report RJ 6439 (62557) 9\/19\/88, IBM Almaden Research Center (1988)"},{"key":"35_CR20","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s101070100268","volume":"92","author":"W.D. Morris","year":"2002","unstructured":"Morris, W.D.: Randomized pivot algorithms for P-matrix linear complementarity problems. Mathematical Programming, Ser. A\u00a092, 285\u2013296 (2002)","journal-title":"Mathematical Programming, Ser. A"},{"key":"35_CR21","volume-title":"Linear Complementarity, Linear and Nonlinear Programming","author":"K.G. Murty","year":"1988","unstructured":"Murty, K.G., Yu, F.-T.: Linear Complementarity, Linear and Nonlinear Programming. Heldermann, Berlin (1988), \n                    \n                      http:\/\/ioe.engin.umich.edu\/people\/fac\/books\/murty\/linear_complementarity_webbook\/"},{"key":"35_CR22","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. Natl. Acad. Sci. U.S.A.\u00a039, 1095\u20131100 (1953)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"35_CR23","unstructured":"Svensson, O., Vorobyov, S.: A subexponential algorithm for a subclass of P-matrix generalized linear complementarity problems. TR DIMACS-2005-20, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ (2005)"},{"key":"35_CR24","unstructured":"Szanc, B.P.: The Generalized Complementarity Problem. PhD thesis, Rensselaer Polytechnic Institute, Troy, New York (1989)"}],"container-title":["Lecture Notes in Computer Science","Perspectives of Systems Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70881-0_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T09:51:20Z","timestamp":1558259480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70881-0_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540708803","9783540708810"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70881-0_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}