{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:15Z","timestamp":1760202735860},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2017,4,7]],"date-time":"2017-04-07T00:00:00Z","timestamp":1491523200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s11590-017-1140-y","type":"journal-article","created":{"date-parts":[[2017,4,7]],"date-time":"2017-04-07T04:52:26Z","timestamp":1491540746000},"page":"1499-1512","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A convex programming-based algorithm for mean payoff stochastic games with perfect information"],"prefix":"10.1007","volume":"11","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":"Vladimir","family":"Gurvich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,7]]},"reference":[{"key":"1140_CR1","doi-asserted-by":"crossref","unstructured":"Andersson, D., Miltersen, P.B.: The complexity of solving stochastic games on graphs. In: Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pp. 112\u2013121 (2009)","DOI":"10.1007\/978-3-642-10631-6_13"},{"key":"1140_CR2","doi-asserted-by":"crossref","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: A pumping algorithm for ergodic stochastic mean payoff games with perfect information. In: Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 341\u2013354 (2010)","DOI":"10.1007\/978-3-642-13036-6_26"},{"issue":"2","key":"1140_CR3","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/s13235-013-0075-x","volume":"3","author":"E Boros","year":"2013","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: On canonical forms for zero-sum stochastic mean payoff games. Dyn. Games Appl. 3(2), 128\u2013161 (2013)","journal-title":"Dyn. Games Appl."},{"key":"1140_CR4","doi-asserted-by":"crossref","unstructured":"Boros, E., Elbassioni, K.M., Gurvich, V., Makino, K.: A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and a few random positions. In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP) Part I, pp. 220\u2013231 (2013)","DOI":"10.1007\/978-3-642-39206-1_19"},{"key":"1140_CR5","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions. CoRR, arXiv:1508.03431 (2015)"},{"key":"1140_CR6","unstructured":"Beffara, E., Vorobyov, S.: Adapting Gurvich\u2013Karzanov\u2013Khachiyan\u2019s Algorithm for Parity Games: Implementation and Experimentation. Technical Report 2001-020, Department of Information Technology, Uppsala University. https:\/\/www.it.uu.se\/research\/reports\/#2001 (2001)"},{"key":"1140_CR7","unstructured":"Beffara, E., Vorobyov, S.: Is Randomized Gurvich\u2013Karzanov\u2013Khachiyan\u2019s Algorithm for Parity Games Polynomial? Technical Report 2001-025. Department of Information Technology, Uppsala University. https:\/\/www.it.uu.se\/research\/reports\/#2001 (2001)"},{"issue":"3","key":"1140_CR8","doi-asserted-by":"crossref","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 sub-exponential algorithm for infinite games. Theor. Comput. Sci. 349(3), 347\u2013360 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1140_CR9","doi-asserted-by":"crossref","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 sub-exponential strategy improvement algorithm for mean payoff games. Discrete Appl. Math. 155(2), 210\u2013229 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1140_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ipl.2007.08.035","volume":"106","author":"K Chatterjee","year":"2008","unstructured":"Chatterjee, K., Henzinger, T.A.: Reduction of stochastic parity to stochastic mean-payoff games. Inf. Process. Lett. 106(1), 1\u20137 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1140_CR11","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/s00453-013-9843-7","volume":"70","author":"K Chatterjee","year":"2014","unstructured":"Chatterjee, K., Henzinger, M., Krinninger, S., Nanongkai, D.: Polynomial-time algorithms for energy games with special weight structures. Algorithmica 70(3), 457\u2013492 (2014)","journal-title":"Algorithmica"},{"key":"1140_CR12","unstructured":"Chatterjee, K., Jurdzi\u0144ski, M., Henzinger, T.A.: Quantitative stochastic parity games. In: SODA \u201904, pp. 121\u201313. Society for Industrial and Applied Mathematics, Philadelphia (2004)"},{"key":"1140_CR13","doi-asserted-by":"crossref","unstructured":"Calude, C.S., Jain, S., Khoussainov, B., Li, W., Stephan, F.: Deciding parity games in quasipolynomial time, to appear in Proceedings of the 49th ACM Symposium on Theory of Computing (STOC) (2017)","DOI":"10.1145\/3055399.3055409"},{"key":"1140_CR14","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A Eherenfeucht","year":"1979","unstructured":"Eherenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. J. Game Theory 8, 109\u2013113 (1979)","journal-title":"Int. J. Game Theory"},{"key":"1140_CR15","first-page":"179","volume-title":"Contribution to the Theory of Games III, in Annals of Mathematics Studies","author":"D Gillette","year":"1957","unstructured":"Gillette, D.: Stochastic games with zero stop probabilities. In: Tucker, A.W., Dresher, M., Wolfe, P. (eds.) Contribution to the Theory of Games III, in Annals of Mathematics Studies, vol. 39, pp. 179\u2013187. Princeton University Press, Princeton (1957)"},{"key":"1140_CR16","doi-asserted-by":"crossref","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 Comput. Math. Math. Phys. 28, 85\u201391 (1988)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"1140_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988)"},{"issue":"1","key":"1140_CR18","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s00453-007-0175-3","volume":"49","author":"N Halman","year":"2007","unstructured":"Halman, N.: Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems. Algorithmica 49(1), 37\u201350 (2007)","journal-title":"Algorithmica"},{"key":"1140_CR19","doi-asserted-by":"crossref","unstructured":"Sandberg, S. Bj\u00f6rklund, H., Vorobyov, S.: A Combinatorial Strongly Sub-Exponential Strategy improvement Algorithm for Mean Payoff Games. DIMACS Technical Report 2004-05. DIMACS, Rutgers University (2004)","DOI":"10.1007\/978-3-540-28629-5_52"},{"key":"1140_CR20","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 117\u2013123. ACM, New York (2006)","DOI":"10.1145\/1109557.1109571"},{"issue":"3","key":"1140_CR21","doi-asserted-by":"crossref","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 $$\\cap $$ \u2229 co-UP. Inf. Process. Lett. 68(3), 119\u2013124 (1998)","journal-title":"Inf. Process. Lett."},{"key":"1140_CR22","unstructured":"Jurdzi\u0144ski, M.: Games for Verification: Algorithmic Issues, Ph.D. thesis. Department of Computer Science, University of Aarhus (2000)"},{"key":"1140_CR23","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"RM Karp","year":"1978","unstructured":"Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Math. 23, 309\u2013311 (1978)","journal-title":"Discrete Math."},{"key":"1140_CR24","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"L Khachiyan","year":"1980","unstructured":"Khachiyan, L.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20, 53\u201372 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"1140_CR25","unstructured":"Khachiyan, L.: Convexity and complexity in polynomial programming. In: Proceedings of the International Congress of Mathematicians, pp. 1569\u20131577. Warsa (1983)"},{"key":"1140_CR26","unstructured":"Khachiyan, L.: Complexity of Convex Problems of Real and Integer Programming, Ph.D. thesis, The second thesis. Manuscript, Computer Center of the USSR Academy of Sciences (in Russian) (1984)"},{"key":"1140_CR27","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01580616","volume":"60","author":"AV Karzanov","year":"1993","unstructured":"Karzanov, A.V., Lebedev, V.N.: Cyclical games with prohibition. Math. Program. 60, 277\u2013293 (1993)","journal-title":"Math. Program."},{"key":"1140_CR28","unstructured":"Littman, M.L.: Algorithm for Sequential Decision Making, CS-96-09, Ph.D. thesis. Deptarment of Computer Science, Brown University (1996)"},{"key":"1140_CR29","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1137\/1011093","volume":"4","author":"TM Liggett","year":"1969","unstructured":"Liggett, T.M., Lippman, S.A.: Stochastic games with perfect information and time-average payoff. SIAM Rev. 4, 604\u2013607 (1969)","journal-title":"SIAM Rev."},{"key":"1140_CR30","volume-title":"Markovian Decision Process","author":"H Mine","year":"1970","unstructured":"Mine, H., Osaki, S.: Markovian Decision Process. American Elsevier Publishing Co., New York (1970)"},{"issue":"2","key":"1140_CR31","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-247X(76)90178-5","volume":"5","author":"H Moulin","year":"1976","unstructured":"Moulin, H.: Extension of two person zero sum games. J. Math. Anal. Appl. 5(2), 490\u2013507 (1976)","journal-title":"J. Math. Anal. Appl."},{"key":"1140_CR32","unstructured":"Moulin, H.: Prolongement des jeux \u00e0 deux joueurs de somme nulle. Bull. Soc. Math. Fr. Mem. 45, 5\u2013111 (1976)"},{"issue":"4","key":"1140_CR33","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1287\/moor.24.4.817","volume":"24","author":"NN Pisaruk","year":"1999","unstructured":"Pisaruk, N.N.: Mean cost cyclical games. Math. Oper. Res. 24(4), 817\u2013828 (1999)","journal-title":"Math. Oper. Res."},{"issue":"6","key":"1140_CR34","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/BF01415989","volume":"35","author":"TES Raghavan","year":"1991","unstructured":"Raghavan, T.E.S., Filar, J.A.: Algorithms for stochastic games: a survey. Math. Methods Oper. Res. 35(6), 437\u2013472 (1991)","journal-title":"Math. Methods Oper. Res."},{"key":"1140_CR35","doi-asserted-by":"crossref","unstructured":"Schewe, S.: From parity and payoff games to linear programming. In: Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia. Proceedings, pp. 675\u2013686 (2009)","DOI":"10.1007\/978-3-642-03816-7_57"},{"issue":"11","key":"1140_CR36","doi-asserted-by":"crossref","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. 156(11), 2195\u20132231 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"1140_CR37","doi-asserted-by":"crossref","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. 158(1\u20132), 343\u2013359 (1996)","journal-title":"Theor. Comput. Sci."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-017-1140-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-017-1140-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-017-1140-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T19:13:57Z","timestamp":1569006837000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-017-1140-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,7]]},"references-count":37,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["1140"],"URL":"https:\/\/doi.org\/10.1007\/s11590-017-1140-y","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,7]]}}}