{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:51:57Z","timestamp":1725490317262},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540738138"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73814-5_9","type":"book-chapter","created":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T05:31:44Z","timestamp":1188624704000},"page":"96-107","source":"Crossref","is-referenced-by-count":11,"title":["On the Approximation and Smoothed Complexity of Leontief Market Equilibria"],"prefix":"10.1007","author":[{"given":"Li-Sha","family":"Huang","sequence":"first","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","unstructured":"Chen, X., Deng, X.: 3-Nash is PPAD-complete. ECCC, TR05-134 (2005)"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the Complexity of 2-Player Nash-Equilibrium. In: The Proceedings of FOCS 2006, pp. 261\u2013272 (2006)","DOI":"10.1109\/FOCS.2006.69"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Computing Nash Equilibria: Approximation and smoothed complexity. In: The Proceedings of FOCS 2006, pp. 603\u2013612 (2006)","DOI":"10.1109\/FOCS.2006.20"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Codenotti, B., Saberi, A., Varadarajan, K., Ye, Y.: Leontief economies encode nonzero sum two-player games. In: The Proceedings of SODA 2006, pp. 659\u2013667 (2006)","DOI":"10.1145\/1109557.1109629"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The Complexity of Computing a Nash Equilibrium. In: The Proceedings of STOC 2006, pp. 71\u201378 (2006)","DOI":"10.1145\/1132516.1132527"},{"key":"9_CR6","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Three-player games are hard. ECCC, TR05-139 (2005)"},{"issue":"2","key":"9_CR7","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0022-0000(03)00011-4","volume":"67","author":"X. Deng","year":"2003","unstructured":"Deng, X., Papadimitriou, C., Safra, S.: On the complexity of price equilibria. Journal of Computer and System Sciences\u00a067(2), 311\u2013324 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR8","unstructured":"Deng, X., Huang, L.-S.: Approximate Economic Equilibrium Algorithms. In: Gonzalez, T. (ed.) Approximation Algorithms and Metaheuristics (2005)"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C.E. Lemke","year":"1964","unstructured":"Lemke, C.E., Howson Jr., J.T.: Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math.\u00a012, 413\u2013423 (1964)","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: The Proceedings of EC 2003, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Noncooperative games. Annals of Mathematics\u00a054, 289\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"issue":"3","key":"9_CR12","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences\u00a048(3), 498\u2013532 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR13","volume-title":"The Computation of Economic Equilibria","author":"H. Scarf","year":"1973","unstructured":"Scarf, H.: The Computation of Economic Equilibria. Yale University Press, New Haven (1973)"},{"issue":"3","key":"9_CR14","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"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms and heuristics: Progress and open questions. In: The Proceedings of Foundations of Computational Mathematics, pp. 274\u2013342 (2006)","DOI":"10.1017\/CBO9780511721571.010"},{"key":"9_CR16","unstructured":"Walras, L.: Elements of Pure Economics, or the Theory of Social Wealth (1874)"},{"key":"9_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/11600930_3","volume-title":"Internet and Network Economics","author":"Y. Ye","year":"2005","unstructured":"Ye, Y.: On exchange market equilibria with Leontief\u2019s utility: Freedom of pricing leads to rationality. In: Deng, X., Ye, Y. (eds.) WINE 2005. LNCS, vol.\u00a03828, pp. 14\u201323. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73814-5_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:00:31Z","timestamp":1619517631000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73814-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540738138"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73814-5_9","relation":{},"subject":[]}}