{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:58:42Z","timestamp":1787507922412,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540404934","type":"print"},{"value":"9783540450610","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_42","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:04Z","timestamp":1184586844000},"page":"514-526","source":"Crossref","is-referenced-by-count":55,"title":["Nashification and the Coordination Ratio for a Selfish Routing Game"],"prefix":"10.1007","author":[{"given":"Rainer","family":"Feldmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Gairing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"L\u00fccking","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Burkhard","family":"Monien","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manuel","family":"Rode","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"42_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0166-218X(96)00036-4","volume":"72","author":"P. Brucker","year":"1997","unstructured":"P. Brucker, J. Hurink, and F. Werner. Improving local search heuristics for some scheduling problems. part ii. Discrete Applied Mathematics, 72:47\u201369, 1997.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"42_CR2","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y. Cho","year":"1980","unstructured":"Y. Cho and S. Sahni. Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9(1):91\u2013103, 1980.","journal-title":"SIAM Journal on Computing"},{"key":"42_CR3","unstructured":"A. Czumaj and B. V\u00f6cking. Tight bounds for worst-case equilibria. In Proc. of SODA 2002, pp 413\u2013420, 2002."},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum, C. Papdimitriou, and S. Shenker. Sharing the cost of multicast transmissions. In Proc. of STOC 2000, pp 218\u2013227, 2000.","DOI":"10.1145\/335305.335332"},{"key":"42_CR5","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01930985","volume":"19","author":"G. Finn","year":"1979","unstructured":"G. Finn and E. Horowitz. A linear time approximation algorithm for multiprocessor scheduling. BIT, 19:312\u2013320, 1979.","journal-title":"BIT"},{"key":"42_CR6","doi-asserted-by":"crossref","unstructured":"D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis. The structure and complexity of nash equilibria for a selfish routing game. In Proc. of ICALP 2002, pp 123\u2013134, 2002.","DOI":"10.1007\/3-540-45465-9_12"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"M. Gairing, T. L\u00fccking, M. Mavronicolas, B. Monien, and P. Spirakis. Extreme nash equilibria. Technical report, FLAGS-TR-03-10, 2002.","DOI":"10.1007\/978-3-540-45208-9_1"},{"issue":"3","key":"42_CR8","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D.S. Hochbaum","year":"1988","unstructured":"D.S. Hochbaum and D. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM Journal on Computing, 17(3):539\u2013551, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"K. Jain and V. Vazirani. Applications of approximation algorithms to cooperative games. In Proc. of STOC 2001, pp 364\u2013372, 2001.","DOI":"10.1145\/380752.380825"},{"issue":"7","key":"42_CR10","doi-asserted-by":"publisher","first-page":"1241","DOI":"10.1109\/49.414643","volume":"13","author":"Y.A. Korilis","year":"1995","unstructured":"Y.A. Korilis, A.A. Lazar, and A. Orda. Architecting noncooperative networks. IEEE Journal on Selected Areas in Communications, 13(7):1241\u20131251, 1995.","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proc. of STACS 1999, pp 404\u2013413, 1999.","DOI":"10.1007\/3-540-49116-3_38"},{"key":"42_CR12","doi-asserted-by":"crossref","unstructured":"M. Mavronicolas and P. Spirakis. The price of selfish routing. In Proc. of STOC 2001, pp 510\u2013519, 2001.","DOI":"10.1145\/380752.380846"},{"key":"42_CR13","doi-asserted-by":"crossref","unstructured":"R.D. McKelvey and A. McLennan. Computation of equilibria in finite games. In H. Amman, D. Kendrick, and J. Rust, editors, Handbook of Computational Economics, 1996.","DOI":"10.1016\/S1574-0021(96)01004-0"},{"issue":"2","key":"42_CR14","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"J. Nash. Non-cooperative games. Annals of Mathematics, 54(2):286\u2013295, 1951.","journal-title":"Annals of Mathematics"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"N. Nisan. Algorithms for selfish agents. In Proc. of STACS 1999, pp 1\u201315, 1999.","DOI":"10.1007\/3-540-49116-3_1"},{"key":"42_CR16","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ronen. Algorithmic mechanism design. In Proc. of STOC 1999, pp 129\u2013140, 1999.","DOI":"10.1145\/301250.301287"},{"key":"42_CR17","unstructured":"M.J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994."},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou. Algorithms, games, and the internet. In Proc. of STOC 2001, pp 749\u2013753, 2001.","DOI":"10.1145\/380752.380883"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"T. Roughgarden and E. Tardos. How bad is selfish routing? In Proc. of FOCS 2000, pp 93\u2013102, 2000.","DOI":"10.1109\/SFCS.2000.892069"},{"key":"42_CR20","doi-asserted-by":"crossref","unstructured":"P. Schuurman and T. Vredeveld. Performance guarantees of load search for multiprocessor scheduling. In Proc. of IPCO 2001, pp 370\u2013382, 2001.","DOI":"10.1007\/3-540-45535-3_29"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:13:51Z","timestamp":1556666031000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_42","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}