{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:15Z","timestamp":1760202675464},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_8","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"89-100","source":"Crossref","is-referenced-by-count":3,"title":["The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average"],"prefix":"10.1007","author":[{"given":"Xavier","family":"Allamigeon","sequence":"first","affiliation":[]},{"given":"Pascal","family":"Benchimol","sequence":"additional","affiliation":[]},{"given":"St\u00e9phane","family":"Gaubert","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"8_CR1","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(1-2), 343\u2013359 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"8_CR2","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 Journal of Game Theory\u00a08(2), 109\u2013113 (1979)","journal-title":"International Journal of Game Theory"},{"issue":"5","key":"8_CR3","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., Khachivan, L.G.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics\u00a028(5), 85\u201391 (1988)","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"issue":"3","key":"8_CR4","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\u2009\u2229\u2009co\u2009\u2212\u2009UP. Information Processing Letters\u00a068(3), 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Gaubert, S., Gunawardena, J.: The duality theorem for min-max functions. C. R. Acad. Sci. Paris\u00a0326(S\u00e9rie I), 43\u201348 (1998)","key":"8_CR5","DOI":"10.1016\/S0764-4442(97)82710-3"},{"key":"8_CR6","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. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol.\u00a01855, pp. 202\u2013215. Springer, Heidelberg (2000)"},{"key":"8_CR7","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 Appl. Math.\u00a0155, 210\u2013229 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"8_CR8","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1137\/070686652","volume":"38","author":"M. Jurdzi\u0144ski","year":"2008","unstructured":"Jurdzi\u0144ski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. SIAM Journal on Computing\u00a038(4), 1519\u20131532 (2008)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Friedmann, O.: An exponential lower bound for the parity game strategy improvement algorithm as we know it. In: LICS, pp. 145\u2013156. IEEE (August 2009)","key":"8_CR9","DOI":"10.1109\/LICS.2009.27"},{"issue":"2","key":"8_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10703-010-0105-x","volume":"38","author":"L. Brim","year":"2011","unstructured":"Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.: Faster algorithms for mean-payoff games. Formal Methods in System Design\u00a038(2), 97\u2013118 (2011)","journal-title":"Formal Methods in System Design"},{"issue":"1","key":"8_CR11","doi-asserted-by":"publisher","first-page":"125001","DOI":"10.1142\/S0218196711006674","volume":"22","author":"M. Akian","year":"2012","unstructured":"Akian, M., Gaubert, S., Guterman, A.: Tropical polyhedra are equivalent to mean payoff games. Int. J. Algebr. Comput.\u00a022(1), 125001 (2012)","journal-title":"Int. J. Algebr. Comput."},{"unstructured":"Allamigeon, X., Benchimol, P., Gaubert, S., Joswig, M.: Tropicalizing the simplex algorithm. E-print arXiv:1308.0454 (2013) (submitted)","key":"8_CR12"},{"unstructured":"Allamigeon, X., Benchimol, P., Gaubert, S., Joswig, M.: Combinatorial simplex algorithms can solve mean payoff games. E-print arXiv:1309.5925 (submitted, 2014)","key":"8_CR13"},{"issue":"4","key":"8_CR14","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1016\/0885-064X(87)90007-0","volume":"3","author":"I. Adler","year":"1987","unstructured":"Adler, I., Karp, R.M., Shamir, R.: A simplex variant solving an m \u00d7d linear program in O( min (m\n                  2,d\n                  2)) expected number of pivot steps. Journal of Complexity\u00a03(4), 372\u2013387 (1987)","journal-title":"Journal of Complexity"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1137\/1.9781611973075.66","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Roth","year":"2010","unstructured":"Roth, A., Balcan, M.F., Kalai, A., Mansour, Y.: On the equilibria of alternating move games. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 805\u2013816. SIAM, Philadelphia (2010)"},{"doi-asserted-by":"crossref","unstructured":"Borgwardt, K.H.: The simplex method: a probabilistic analysis. Algorithms and Combinatorics, vol.\u00a01. Springer (1987)","key":"8_CR16","DOI":"10.1007\/978-3-642-61578-8_1"},{"key":"8_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4771-1","volume-title":"Discriminants, Resultants, and Multidimensional Determinants. Mathematics: Theory & Applications","author":"I.M. Gelfand","year":"1994","unstructured":"Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants, Resultants, and Multidimensional Determinants. Mathematics: Theory & Applications. Birkh\u00e4user, Boston (1994)"},{"issue":"3","key":"8_CR18","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"}],"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-662-43948-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:22:21Z","timestamp":1558909341000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}