{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:27Z","timestamp":1760202627468},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_13","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T03:44:05Z","timestamp":1308541445000},"page":"147-158","source":"Crossref","is-referenced-by-count":11,"title":["Stochastic Mean Payoff Games: Smoothed\u00a0Analysis\u00a0and\u00a0Approximation\u00a0Schemes"],"prefix":"10.1007","author":[{"given":"Endre","family":"Boros","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khaled","family":"Elbassioni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahmoud","family":"Fouz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Gurvich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_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)"},{"issue":"4","key":"13_CR2","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1137\/S0097539705447268","volume":"35","author":"R. Beier","year":"2006","unstructured":"Beier, R., V\u00f6cking, B.: Typical properties of winners and losers in discrete optimization. SIAM J. Comput.\u00a035(4), 855\u2013881 (2006)","journal-title":"SIAM J. Comput."},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-642-13036-6_26","volume-title":"Integer Programming and Combinatorial Optimization","author":"E. Boros","year":"2010","unstructured":"Boros, E., Elbassioni, K.M., Gurvich, V., Makino, K.: A pumping algorithm for ergodic stochastic mean payoff games with perfect information. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 341\u2013354. Springer, Heidelberg (2010)"},{"key":"13_CR4","series-title":"Annals of Mathematics Studies","first-page":"179","volume-title":"Contribution to the Theory of Games III","author":"D. Gillette","year":"1957","unstructured":"Gillette, D.: Stochastic games with zero stop probabilities. In: Dresher, M., Tucker, A.W., Wolfe, P. (eds.) Contribution to the Theory of Games III. Annals of Mathematics Studies, vol.\u00a039, pp. 179\u2013187. Princeton University Press, Princeton (1957)"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"V. Gurvich","year":"1988","unstructured":"Gurvich, V., Karzanov, A., Khachiyan, L.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics\u00a028, 85\u201391 (1988)","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"issue":"5","key":"13_CR6","first-page":"359","volume":"12","author":"A.J. Hoffman","year":"1966","unstructured":"Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Management Science, Series A\u00a012(5), 359\u2013370 (1966)","journal-title":"Management Science, Series A"},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01580616","volume":"60","author":"A.V. Karzanov","year":"1993","unstructured":"Karzanov, A.V., Lebedev, V.N.: Cyclical games with prohibition. Mathematical Programming\u00a060, 277\u2013293 (1993)","journal-title":"Mathematical Programming"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1137\/1011093","volume":"4","author":"T.M. Liggett","year":"1969","unstructured":"Liggett, T.M., Lippman, S.A.: Stochastic games with perfect information and time-average payoff. SIAM Review\u00a04, 604\u2013607 (1969)","journal-title":"SIAM Review"},{"key":"13_CR9","volume-title":"Markovian decision process","author":"H. Mine","year":"1970","unstructured":"Mine, H., Osaki, S.: Markovian decision process. Elsevier, Amsterdam (1970)"},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica\u00a07(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Roth, A., Balcan, M.-F., Kalai, A., Mansour, Y.: On the equilibria of alternating move games. In: SODA, pp. 805\u2013816 (2010)","DOI":"10.1137\/1.9781611973075.66"},{"issue":"3","key":"13_CR12","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"issue":"10","key":"13_CR13","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"D.A. Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis: An attempt to explain the behavior of algorithms in practice. C. ACM\u00a052(10), 76\u201384 (2009)","journal-title":"C. ACM"},{"issue":"11","key":"13_CR14","doi-asserted-by":"publisher","first-page":"2195","DOI":"10.1016\/j.dam.2008.04.012","volume":"156","author":"S. Vorobyov","year":"2008","unstructured":"Vorobyov, S.: Cyclic games and linear programming. Discrete Appl. Math.\u00a0156(11), 2195\u20132231 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"1-2","key":"13_CR15","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. Theoret. Comput. Sci.\u00a0158(1-2), 343\u2013359 (1996)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T03:04:11Z","timestamp":1553828651000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}