{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T09:27:36Z","timestamp":1748856456664},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281931"},{"type":"electronic","value":"9783540318736"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11537311_19","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T14:00:06Z","timestamp":1127829606000},"page":"209-220","source":"Crossref","is-referenced-by-count":14,"title":["Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems"],"prefix":"10.1007","author":[{"given":"Bernd","family":"G\u00e4rtner","sequence":"first","affiliation":[]},{"given":"Leo","family":"R\u00fcst","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Shapley, S.: Stochastic games. Proceedings of the National Academy of Science U.S.A. 39, 1095\u20131100. (1953)","DOI":"10.1073\/pnas.39.10.1953"},{"key":"19_CR2","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 & Computation\u00a096, 203\u2013224 (1992)","journal-title":"Information & Computation"},{"key":"19_CR3","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. Theor. Comput. Sci.\u00a0158, 343\u2013359 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR4","unstructured":"Puri, A.: Theory of hybrid systems and discrete event systems. PhD thesis, University of California at Berkeley (1995)"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Condon, A.: On algorithms for simple stochastic games. In: Cai, J.Y. (ed.) 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":"19_CR6","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1006\/inco.1995.1035","volume":"117","author":"W. Ludwig","year":"1995","unstructured":"Ludwig, W.: A subexponential randomized algorithm for the simple stochastic game problem. Information and Computation\u00a0117, 151\u2013155 (1995)","journal-title":"Information and Computation"},{"key":"19_CR7","unstructured":"Bj\u00f6rklund, H., Sandberg, S., Vorobyov, S.: Randomized subexponential algorithms for infinite games. Technical Report 2004-09, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ (2004)"},{"key":"19_CR8","unstructured":"Halman, N.: Discrete and Lexicographic Helly Theorems and Their Relations to LP-type problems. PhD thesis, Tel-Aviv University (2004)"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Kalai, G.: A subexponential randomized simplex algorithm. In: Proc. 24th annu. ACM Symp. on Theory of Computing, pp. 475\u2013482 (1992)","DOI":"10.1145\/129712.129759"},{"key":"19_CR10","first-page":"217","volume":"79","author":"G. Kalai","year":"1997","unstructured":"Kalai, G.: Linear programming, the simplex algorithm and simple polytopes. Math. Programming\u00a079, 217\u2013233 (1997)","journal-title":"Math. Programming"},{"key":"19_CR11","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, E.: A subexponential bound for linear programming. Algorithmica\u00a016, 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"19_CR12","unstructured":"Halman, N.: An EGLP formulation for the simple stochastic game problem, or a comment on the paper: A subexponential randomized algorithm for the Simple Stochastic Game problem by W. Ludwig. Technical Report RP-SOR-01-02, Department of Statistics and Operations Research (2001)"},{"key":"19_CR13","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 on Combinatorial Theory\u00a08, 79\u201390 (1970)","journal-title":"Journal on Combinatorial Theory"},{"key":"19_CR14","volume-title":"Handbook of Game Theory.","author":"B. Stengel von","year":"2002","unstructured":"von Stengel, B.: Computing equilibria for two-person games. In: Handbook of Game Theory, vol.\u00a03. Elsevier Science Publishers, North-Holland (2002)"},{"key":"19_CR15","volume-title":"The Linear Complementarity Problem","author":"R.W. Cottle","year":"1992","unstructured":"Cottle, R.W., Pang, J., Stone, R.E.: The Linear Complementarity Problem. Academic Press, London (1992)"},{"key":"19_CR16","unstructured":"Szanc, B.P.: The Generalized Complementarity Problem. PhD thesis, Rensselaer Polytechnic Institute, Troy, NY (1989)"},{"key":"19_CR17","unstructured":"Megiddo, N.: A note on the complexity of P-matrix LCP and computing an equilibrium. Technical report, IBM Almaden Research Center, San Jose (1988)"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/11496915_16","volume-title":"Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO)","author":"B. G\u00e4rtner","year":"2005","unstructured":"G\u00e4rtner, B., Morris Jr., W.D.R., R\u00fcst, L.: Unique sink orientations of grids. In: J\u00fcnger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol.\u00a03509, pp. 210\u2013224. Springer, Heidelberg (2005)"},{"key":"19_CR19","unstructured":"Bj\u00f6rklund, H., Svensson, O., Vorobyov, S.: Controlled linear programming for infinite games. Technical Report 2005-13, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ (2005)"},{"key":"19_CR20","unstructured":"Bj\u00f6rklund, H., Svensson, O., Vorobyov, S.: Linear complementarity algorithms for mean payoff games. Technical Report 2005-05, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ (2005)"},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/S0895479894271147","volume":"18","author":"S.R. Mohan","year":"1997","unstructured":"Mohan, S.R., Neogy, S.K.: Vertical block hidden Z-matrices and the generalized linear complementarity problem. SIAM J. Matrix Anal. Appl.\u00a018, 181\u2013190 (1997)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"19_CR22","first-page":"231","volume-title":"Constructive Approaches to Mathematical Models. Proceedings of a conference in honor of R. J. Duffin","author":"J. Pang","year":"1979","unstructured":"Pang, J.: On discovering hidden Z-matrices. In: Coffman, C.V., Fix, G.J. (eds.) Constructive Approaches to Mathematical Models. Proceedings of a conference in honor of R. J. Duffin, pp. 231\u2013241. Academic Press, New York (1979)"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01580671","volume":"10","author":"O.L. Mangasarian","year":"1976","unstructured":"Mangasarian, O.L.: Linear complementarity problems solvable by a single linear program. Math. Program.\u00a010, 263\u2013270 (1976)","journal-title":"Math. Program."},{"key":"19_CR24","first-page":"393","volume":"31","author":"O.L. Mangasarian","year":"1979","unstructured":"Mangasarian, O.L.: Generalized linear complementarity problems as linear programs. Oper. Res.-Verf.\u00a031, 393\u2013402 (1979)","journal-title":"Oper. Res.-Verf."},{"key":"19_CR25","unstructured":"G\u00e4rtner, B., R\u00fcst, L.: Properties of vertical block matrices. Manuscript (2005)"},{"key":"19_CR26","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0024-3795(99)00281-5","volume":"307","author":"M.J. Tsatsomeros","year":"2000","unstructured":"Tsatsomeros, M.J.: Principal pivot transforms: Properties and applications. Linear Algebra and Its Applications\u00a0307, 151\u2013165 (2000)","journal-title":"Linear Algebra and Its Applications"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11537311_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:12:21Z","timestamp":1605643941000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11537311_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281931","9783540318736"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/11537311_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}