{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T15:22:18Z","timestamp":1725895338662},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642339950"},{"type":"electronic","value":"9783642339967"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33996-7_14","type":"book-chapter","created":{"date-parts":[[2012,10,6]],"date-time":"2012-10-06T03:27:01Z","timestamp":1349494021000},"page":"156-167","source":"Crossref","is-referenced-by-count":3,"title":["On the Hardness of Network Design for Bottleneck Routing Games"],"prefix":"10.1007","author":[{"given":"Dimitris","family":"Fotakis","sequence":"first","affiliation":[]},{"given":"Alexis C.","family":"Kaporis","sequence":"additional","affiliation":[]},{"given":"Thanasis","family":"Lianeas","sequence":"additional","affiliation":[]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0024-3795(94)90357-3","volume":"99","author":"I. Alth\u00f6fer","year":"1994","unstructured":"Alth\u00f6fer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra and Applications\u00a099, 339\u2013355 (1994)","journal-title":"Linear Algebra and Applications"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/11671411_4","volume-title":"Approximation and Online Algorithms","author":"Y. Azar","year":"2006","unstructured":"Azar, Y., Epstein, A.: The Hardness of Network Design for Unsplittable Flow with Selfish Users. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol.\u00a03879, pp. 41\u201354. Springer, Heidelberg (2006)"},{"issue":"6","key":"14_CR3","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1109\/JSAC.2007.070811","volume":"25","author":"R. Banner","year":"2007","unstructured":"Banner, R., Orda, A.: Bottleneck routing games in communication networks. IEEE Journal on Selected Areas in Communications\u00a025(6), 1173\u20131179 (2007)","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"14_CR4","first-page":"258","volume":"12","author":"D. Braess","year":"1968","unstructured":"Braess, D.: \u00dcber ein paradox aus der Verkehrsplanung. Unternehmensforschung\u00a012, 258\u2013268 (1968)","journal-title":"Unternehmensforschung"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"3337","DOI":"10.1016\/j.tcs.2009.04.015","volume":"410","author":"C. Busch","year":"2009","unstructured":"Busch, C., Magdon-Ismail, M.: Atomic routing games on maximum congestion. Theoretical Computer Science\u00a0410, 3337\u20133347 (2009)","journal-title":"Theoretical Computer Science"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1007\/11602613_81","volume-title":"Algorithms and Computation","author":"I. Caragiannis","year":"2005","unstructured":"Caragiannis, I., Galdi, C., Kaklamanis, C.: Network Load Games. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 809\u2013818. Springer, Heidelberg (2005)"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Cole, R., Dodis, Y., Roughgarden, T.: Bottleneck links, variable demand, and the tragedy of the commons. In: Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pp. 668\u2013677 (2006)","DOI":"10.1145\/1109557.1109630"},{"issue":"1","key":"14_CR8","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.geb.2008.04.011","volume":"66","author":"A. Epstein","year":"2009","unstructured":"Epstein, A., Feldman, M., Mansour, Y.: Efficient graph topologies in network routing games. Games and Economic Behaviour\u00a066(1), 115\u2013125 (2009)","journal-title":"Games and Economic Behaviour"},{"key":"14_CR9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theoretical Computer Science\u00a010, 111\u2013121 (1980)","journal-title":"Theoretical Computer Science"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Kaporis, A.C., Lianeas, T., Spirakis, P.: On the hardness of network design for bottleneck routing games. CoRR, abs\/1207.5212 (2012)","DOI":"10.1007\/978-3-642-33996-7_14"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-642-02930-1_38","volume-title":"Automata, Languages and Programming","author":"D. Fotakis","year":"2009","unstructured":"Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Efficient Methods for Selfish Network Design. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol.\u00a05556, pp. 459\u2013471. Springer, Heidelberg (2009)"},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-540-72504-6_5","volume-title":"Theory and Applications of Models of Computation","author":"H. Hou","year":"2007","unstructured":"Hou, H., Zhang, G.: The Hardness of Selective Network Design for Bottleneck Routing Games. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol.\u00a04484, pp. 58\u201366. Springer, Heidelberg (2007)"},{"key":"14_CR13","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.\u00a01563, pp. 404\u2013413. Springer, Heidelberg (1999)"},{"key":"14_CR14","unstructured":"Lin, H., Roughgarden, T., Tardos, \u00c9.: A stronger bound on Braess\u2019s paradox. In: Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 340\u2013341 (2004)"},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/11523468_41","volume-title":"Automata, Languages and Programming","author":"H. Lin","year":"2005","unstructured":"Lin, H., Roughgarden, T., Tardos, \u00c9., Walkover, A.: Braess\u2019s Paradox, Fibonacci Numbers, and Exponential Inapproximability. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 497\u2013512. Springer, Heidelberg (2005)"},{"key":"14_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/11944874_30","volume-title":"Internet and Network Economics","author":"V. Mazalov","year":"2006","unstructured":"Mazalov, V., Monien, B., Schoppmann, F., Tiemann, K.: Wardrop Equilibria and Price of Stability for Bottleneck Games with Splittable Traffic. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol.\u00a04286, pp. 331\u2013342. Springer, Heidelberg (2006)"},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.geb.2005.09.005","volume":"57","author":"I. Milchtaich","year":"2006","unstructured":"Milchtaich, I.: Network topology and the efficiency of equilibrium. Games and Economic Behavior\u00a057, 321\u2013346 (2006)","journal-title":"Games and Economic Behavior"},{"issue":"5","key":"14_CR18","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1016\/j.jcss.2005.05.009","volume":"72","author":"T. Roughgarden","year":"2006","unstructured":"Roughgarden, T.: On the severity of Braess\u2019s paradox: Designing networks for selfish users is hard. Journal of Computer and System Sciences\u00a072(5), 922\u2013953 (2006)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33996-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T23:58:13Z","timestamp":1557273493000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33996-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642339950","9783642339967"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33996-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}