{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T00:38:25Z","timestamp":1725842305756},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662489949"},{"type":"electronic","value":"9783662489956"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.5"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48995-6_9","type":"book-chapter","created":{"date-parts":[[2015,12,8]],"date-time":"2015-12-08T18:37:29Z","timestamp":1449599849000},"page":"118-131","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions"],"prefix":"10.1007","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Michele","family":"Flammini","sequence":"additional","affiliation":[]},{"given":"Gianpiero","family":"Monaco","sequence":"additional","affiliation":[]},{"given":"Luca","family":"Moscardelli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,12,30]]},"reference":[{"issue":"6","key":"9_CR1","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1455248.1455249","volume":"55","author":"H Ackermann","year":"2008","unstructured":"Ackermann, H., R\u00f6glin, H., V\u00f6cking, B.: On the impact of combinatorial structure on congestion games. J. ACM 55(6), 25 (2008)","journal-title":"J. ACM"},{"issue":"4","key":"9_CR2","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1080\/15427951.2012.754800","volume":"9","author":"S Albers","year":"2013","unstructured":"Albers, S., Lenzner, P.: On approximate Nash equilibria in network design. Internet Math. 9(4), 384\u2013405 (2013)","journal-title":"Internet Math."},{"issue":"4","key":"9_CR3","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/070680096","volume":"38","author":"E Anshelevich","year":"2008","unstructured":"Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602\u20131623 (2008)","journal-title":"SIAM J. Comput."},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Caragiannis, V., Fanelli, A., Gravin, N., Skopalik, A.: Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games. In: Proceedings of the IEEE 52nd Symposium on Foundations of Computer Science (FOCS), pp. 532\u2013541 (2011)","DOI":"10.1109\/FOCS.2011.50"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73\u201391 (1999)","journal-title":"J. Algorithms"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-642-25510-6_23","volume-title":"Internet and Network Economics","author":"F Magniez","year":"2011","unstructured":"Magniez, F., de Rougemont, M., Santha, M., Zeitoun, X.: The complexity of approximate Nash equilibrium in congestion games with negative delays. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) Internet and Network Economics. LNCS, vol. 7090, pp. 266\u2013277. Springer, Heidelberg (2011)"},{"key":"9_CR7","unstructured":"Chien, S., Sinclair, A.: Convergence to Approximate Nash Equilibria in Congestion Games. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 169\u2013178. ACM Press (2007)"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 604\u2013612 (2004)","DOI":"10.1145\/1007352.1007445"},{"key":"9_CR9","unstructured":"Feige, U.: A threshold of $$\\log n$$ for approximating set-cover. In: Proceedings of the 28th ACM Symposium on Theory of Computing (STOC), pp. 314\u2013318 (1996)"},{"issue":"1","key":"9_CR10","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/j.jcss.2011.05.009","volume":"78","author":"M Feldman","year":"2012","unstructured":"Feldman, M., Kortsarz, G., Nutov, Z.: Improved approximation algorithms for Directed Steiner Forest. J. Comput. Syst. Sci. 78(1), 279\u2013292 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9_CR11","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D Johnson","year":"1988","unstructured":"Johnson, D., Papadimitriou, C., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/3-540-49116-3_38","volume-title":"STACS 99","author":"E Koutsoupias","year":"1999","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404\u2013413. Springer, Heidelberg (1999)"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer, D., Shapley, L.: Potential games. Games Econ. Behav. 14, 124\u2013143 (1996)","journal-title":"Games Econ. Behav."},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Nash, J.F.: Equilibrium points in $$n$$-person games. In: Proceedings of the National Academy of Sciences, vol. 36, pp. 48-49 (1950)","DOI":"10.1073\/pnas.36.1.48"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. In: Procedings of ACM Symposium on Theory of Computing (STOC), pp. 229\u2013234 (1988)","DOI":"10.1145\/62212.62233"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"R Rosenthal","year":"1973","unstructured":"Rosenthal, R.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65\u201367 (1973)","journal-title":"Int. J. Game Theory"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Skopalik, A., V\u00f6cking, B.: Inapproximability of pure Nash equilibria. In: Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pp. 355\u2013364 (2008)","DOI":"10.1145\/1374376.1374428"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-642-17572-5_30","volume-title":"Internet and Network Economics","author":"V Syrgkanis","year":"2010","unstructured":"Syrgkanis, V.: The complexity of equilibria in cost sharing games. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 366\u2013377. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48995-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,28]],"date-time":"2023-12-28T09:11:25Z","timestamp":1703754685000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48995-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662489949","9783662489956"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48995-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"30 December 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}