{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:56:27Z","timestamp":1743101787263,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029295"},{"type":"electronic","value":"9783642029301"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02930-1_38","type":"book-chapter","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T11:05:04Z","timestamp":1246532704000},"page":"459-471","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Methods for Selfish Network Design"],"prefix":"10.1007","author":[{"given":"Dimitris","family":"Fotakis","sequence":"first","affiliation":[]},{"given":"Alexis C.","family":"Kaporis","sequence":"additional","affiliation":[]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. John Wiley, Chichester (1992)"},{"key":"38_CR2","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":"38_CR3","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)"},{"key":"38_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-540-92185-1_31","volume-title":"Internet and Network Economics","author":"V. Bonifaci","year":"2008","unstructured":"Bonifaci, V., Harks, T., Sch\u00e4fer, G.: Stackelberg Routing in Arbitrary Networks. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol.\u00a05385, pp. 239\u2013250. Springer, Heidelberg (2008)"},{"key":"38_CR5","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":"38_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/11841036_19","volume-title":"Algorithms \u2013 ESA 2006","author":"I. Caragiannis","year":"2006","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Taxes for Linear Atomic Congestion Games. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 184\u2013195. Springer, Heidelberg (2006)"},{"issue":"3","key":"38_CR7","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1016\/j.jcss.2005.09.010","volume":"72","author":"R. Cole","year":"2006","unstructured":"Cole, R., Dodis, Y., Roughgarden, T.: How Much Can Taxes Help Selfish Routing? J. Comput. System Sci.\u00a072(3), 444\u2013467 (2006)","journal-title":"J. Comput. System Sci."},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Fleischer, L., Jain, K., Mahdian, M.: Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games. In: Proc. of FOCS 2004, pp. 277\u2013285 (2004)","DOI":"10.1109\/FOCS.2004.69"},{"key":"38_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-540-75520-3_28","volume-title":"Algorithms \u2013 ESA 2007","author":"D. Fotakis","year":"2007","unstructured":"Fotakis, D.: Stackelberg Strategies for Atomic Congestion Games. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 299\u2013310. Springer, Heidelberg (2007)"},{"key":"38_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-540-77105-0_19","volume-title":"Internet and Network Economics","author":"D. Fotakis","year":"2007","unstructured":"Fotakis, D., Spirakis, P.: Cost-Balancing Tolls for Atomic Network Congestion Games. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol.\u00a04858, pp. 179\u2013190. Springer, Heidelberg (2007)"},{"issue":"4","key":"38_CR11","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/96559.96597","volume":"37","author":"D.S. Hochbaum","year":"1990","unstructured":"Hochbaum, D.S., Shanthikumar, J.G.: Convex Separable Optimization is not Much Harder than Linear Optimization. J. ACM\u00a037(4), 843\u2013862 (1990)","journal-title":"J. ACM"},{"issue":"301","key":"38_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association\u00a058(301), 13\u201330 (1963)","journal-title":"Journal of the American Statistical Association"},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"Kaporis, A.C., Spirakis, P.G.: The Price of Optimum in Stackelberg Games on Arbitrary Single Commodity Networks and Latency Functions. In: Proc. of SPAA 2006, pp. 19\u201328 (2006)","DOI":"10.1145\/1148109.1148113"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"Karakostas, G., Kolliopoulos, S.: Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users. In: Proc. of FOCS 2004, pp. 268\u2013276 (2004)","DOI":"10.1109\/FOCS.2004.26"},{"issue":"1","key":"38_CR15","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/s00453-007-9018-5","volume":"53","author":"G. Karakostas","year":"2009","unstructured":"Karakostas, G., Kolliopoulos, S.: Stackelberg Strategies for Selfish Routing in General Multicommodity Networks. Algorithmica\u00a053(1), 132\u2013153 (2009)","journal-title":"Algorithmica"},{"issue":"1","key":"38_CR16","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1109\/90.554730","volume":"5","author":"Y.A. Korilis","year":"1997","unstructured":"Korilis, Y.A., Lazar, A.A., Orda, A.: Achieving Network Optima Using Stackelberg Routing Strategies. IEEE\/ACM Trans. on Networking\u00a05(1), 161\u2013173 (1997)","journal-title":"IEEE\/ACM Trans. on Networking"},{"key":"38_CR17","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":"38_CR18","unstructured":"Lin, H., Roughgarden, T., Tardos, \u00c9.: A Stronger Bound on Braess\u2019s Paradox. In: Proc. of SODA 2004, pp. 340\u2013341 (2004)"},{"key":"38_CR19","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":"38_CR20","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing Large Games Using Simple Strategies. In: Proc. of EC 2003, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"key":"38_CR21","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Young, N.E.: Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory. In: Proc. of STOC 1994, pp. 734\u2013740 (1994)","DOI":"10.1145\/195058.195447"},{"key":"38_CR22","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0024-3795(79)90014-4","volume":"25","author":"O.L. Mangasarian","year":"1979","unstructured":"Mangasarian, O.L.: Uniqueness of Solution on Linear Programming. Linear Algebra and its Applications\u00a025, 151\u2013162 (1979)","journal-title":"Linear Algebra and its Applications"},{"key":"38_CR23","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":"3","key":"38_CR24","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/0377-2217(84)90160-7","volume":"18","author":"M. Minoux","year":"1984","unstructured":"Minoux, M.: A Polynomial Algorithm for Minimum Quadratic Cost Flow Problems. European J. of Operational Research\u00a018(3), 377\u2013387 (1984)","journal-title":"European J. of Operational Research"},{"issue":"2","key":"38_CR25","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T. Roughdarden","year":"2002","unstructured":"Roughdarden, T., Tardos, \u00c9.: How Bad is Selfish Routing? J. ACM\u00a049(2), 236\u2013259 (2002)","journal-title":"J. ACM"},{"key":"38_CR26","doi-asserted-by":"crossref","unstructured":"Roughgarden, T.: The Price of Anarchy is Independent of the Network Topology. In: Proc. of STOC 2002, pp. 428\u2013437 (2002)","DOI":"10.1145\/509907.509971"},{"issue":"2","key":"38_CR27","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/S0097539701397059","volume":"33","author":"T. Roughgarden","year":"2004","unstructured":"Roughgarden, T.: Stackelberg Scheduling Strategies. SIAM J. on Computing\u00a033(2), 332\u2013350 (2004)","journal-title":"SIAM J. on Computing"},{"key":"38_CR28","volume-title":"Selfish Routing and the Price of Anarchy","author":"T. Roughgarden","year":"2005","unstructured":"Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge (2005)"},{"issue":"5","key":"38_CR29","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. J. Comput. System Sci.\u00a072(5), 922\u2013953 (2006)","journal-title":"J. Comput. System Sci."},{"key":"38_CR30","doi-asserted-by":"crossref","unstructured":"Valiant, G., Roughgarden, T.: Braess\u2019s Paradox in Large Random Graphs. In: Proc. of EC 2006, pp. 296\u2013305 (2006)","DOI":"10.1145\/1134707.1134740"}],"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-642-02930-1_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T20:20:41Z","timestamp":1552076441000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02930-1_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029295","9783642029301"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02930-1_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}