{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:48:44Z","timestamp":1760298524832},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,5,15]],"date-time":"2012-05-15T00:00:00Z","timestamp":1337040000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00224-012-9411-6","type":"journal-article","created":{"date-parts":[[2012,5,14]],"date-time":"2012-05-14T06:27:28Z","timestamp":1336976848000},"page":"668-686","source":"Crossref","is-referenced-by-count":22,"title":["Improved Lower Bounds on the Price of Stability of Undirected Network Design Games"],"prefix":"10.1007","volume":"52","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis","family":"Caragiannis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Fanelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianpiero","family":"Monaco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,5,15]]},"reference":[{"issue":"6","key":"9411_CR1","doi-asserted-by":"crossref","first-page":"2273","DOI":"10.1137\/070701376","volume":"38","author":"S. Albers","year":"2009","unstructured":"Albers, S.: On the value of coordination in network design. SIAM J. Comput. 38(6), 2273\u20132302 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9411_CR2","doi-asserted-by":"crossref","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":"9411_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/11786986_28","volume-title":"Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP)","author":"I. Caragiannis","year":"2006","unstructured":"Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP). LNCS, vol.\u00a04051, pp.\u00a0311\u2013322. Springer, Berlin (2006)"},{"key":"9411_CR4","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/s00224-008-9128-8","volume":"45","author":"H.-L. Chen","year":"2009","unstructured":"Chen, H.-L., Roughgarden, T.: Network design with weighted players. Theory Comput. Syst. 45, 302\u2013324 (2009)","journal-title":"Theory Comput. Syst."},{"key":"9411_CR5","series-title":"LNCS","first-page":"59","volume-title":"Proceedings of the 13th Annual European Symposium on Algorithms (ESA)","author":"G. Christodoulou","year":"2005","unstructured":"Christodoulou, G., Koutsoupias, E.: The price of anarchy and stability of correlated equilibria of linear congestion games. In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA). LNCS, vol.\u00a03669, pp.\u00a059\u201370. Springer, Berlin (2005)"},{"key":"9411_CR6","series-title":"LNCS","first-page":"86","volume-title":"Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA)","author":"G. Christodoulou","year":"2009","unstructured":"Christodoulou, G., Chung, C., Ligett, K., Pyrga, E., van Stee, R.: On the price of stability for undirected network design. In: Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA). LNCS, vol.\u00a05893, pp.\u00a086\u201397. Springer, Berlin (2009)"},{"key":"9411_CR7","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1007\/11786986_53","volume-title":"Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP)","author":"A. Fiat","year":"2006","unstructured":"Fiat, A., Kaplan, H., Levy, M., Olonetsky, S., Shabo, R.: On the price of stability for designing undirected networks with fair cost allocations. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP). LNCS, vol.\u00a04051, pp.\u00a0608\u2013618. Springer, Berlin (2006)"},{"key":"9411_CR8","series-title":"LNCS","first-page":"404","volume-title":"Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"E. Koutsoupias","year":"1999","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS). LNCS, vol.\u00a01563, pp.\u00a0404\u2013413. Springer, Berlin (1999)"},{"issue":"15","key":"9411_CR9","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1016\/j.ipl.2009.04.015","volume":"109","author":"J. Li","year":"2009","unstructured":"Li, J.: An O(logn\/loglogn) upper bound on the price of stability for undirected Shapley network design games. Inf. Process. Lett. 109(15), 876\u2013878 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9411_CR10","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1145\/380752.380883","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC)","author":"C.H. Papadimitriou","year":"2001","unstructured":"Papadimitriou, C.H.: Algorithms, games and the internet. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp.\u00a0749\u2013753 (2001)"},{"key":"9411_CR11","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"R. Rosenthal","year":"1973","unstructured":"Rosenthal, R.: A\u00a0class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65\u201367 (1973)","journal-title":"Int. J. Game Theory"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9411-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9411-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9411-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:24Z","timestamp":1558698864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9411-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,15]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9411"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9411-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,15]]}}}