{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T20:13:04Z","timestamp":1773778384493,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,8,13]],"date-time":"2009-08-13T00:00:00Z","timestamp":1250121600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s00453-009-9348-6","type":"journal-article","created":{"date-parts":[[2009,8,12]],"date-time":"2009-08-12T17:18:38Z","timestamp":1250097518000},"page":"368-394","source":"Crossref","is-referenced-by-count":51,"title":["Selfish Bin Packing"],"prefix":"10.1007","volume":"60","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[]},{"given":"Elena","family":"Kleiman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,13]]},"reference":[{"key":"9348_CR1","unstructured":"Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. In: Proc. of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 189\u2013198 (2007)"},{"key":"9348_CR2","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Dasgupta, A., Tardos, \u00c9., Wexler, T.: Near-optimal network design with selfish agents. In: Proc. of the 35th Annual ACM Symposium on Theory of Computing, STOC 2003, pp. 511\u2013520 (2003)","DOI":"10.1145\/780615.780617"},{"key":"9348_CR3","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, \u00c9., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proc. of the 45th Symposium on Foundations of Computer Science FOCS 2004, pp. 295\u2013304 (2004)","DOI":"10.1109\/FOCS.2004.68"},{"key":"9348_CR4","series-title":"Annals of Mathematics Study","first-page":"287","volume-title":"Contributions to the Theory of Games IV","author":"R.J. Aumann","year":"1959","unstructured":"Aumann, R.J.: Acceptable points in general cooperative n-person games. In: Tucker, A.W., Luce, R.D. (eds.) Contributions to the Theory of Games IV. Annals of Mathematics Study, vol. 40, pp. 287\u2013324. Princeton University Press, Princeton (1959)"},{"key":"9348_CR5","volume-title":"Proc. of the 20th International Parallel and Distributed Processing Symposium, IPDPS 2006","author":"V. Bil\u00f2","year":"2006","unstructured":"Bil\u00f2, V.: On the packing of selfish items. In: Proc. of the 20th International Parallel and Distributed Processing Symposium, IPDPS 2006. IEEE, New York (2006)"},{"issue":"2","key":"9348_CR6","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0167-6377(03)00092-0","volume":"32","author":"A. Caprara","year":"2004","unstructured":"Caprara, A., Pferschy, U.: Worst-case analysis of the subset sum algorithm for bin packing. Oper. Res. Lett. 32(2), 159\u2013166 (2004)","journal-title":"Oper. Res. Lett."},{"key":"9348_CR7","first-page":"1","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"E. Coffman Jr.","year":"2007","unstructured":"Coffman, E. Jr., Csirik, J.: Performance guarantees for one-dimensional bin packing. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics, Chap.\u00a032. pp. 1\u201318. Chapman & Hall, London (2007)"},{"key":"9348_CR8","volume-title":"Algorithm Design for Computer Systems Design","author":"E. Coffman Jr.","year":"1984","unstructured":"Coffman, E. Jr., Garey, M., Johnson, D.: Approximation algorithms for bin-packing: an updated survey. In: Ausiello, G., Lucertini, M., Serafini, P. (eds.) Algorithm Design for Computer Systems Design. Springer, New York (1984)"},{"key":"9348_CR9","volume-title":"Handbook of Combinatorial Optimization","author":"E Coffman Jr.","year":"1998","unstructured":"Coffman, E Jr., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: combinatorial analysis. In: Handbook of Combinatorial Optimization. Kluwer Academic, Amsterdam (1998)"},{"key":"9348_CR10","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"A. Czumaj","year":"2004","unstructured":"Czumaj, A.: Selfish routing on the Internet. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chap.\u00a042. CRC, Boca Raton (2004)"},{"key":"9348_CR11","doi-asserted-by":"crossref","unstructured":"Czumaj, A., V\u00f6cking, B.: Tight bounds for worst-case equilibria. ACM Trans. Algorithms 3(1), 2007","DOI":"10.1145\/1186810.1186814"},{"key":"9348_CR12","doi-asserted-by":"crossref","unstructured":"Epstein, L., Kleiman, E.: Selfish bin packing. In: Proc. of the 16th Annual European Symposium on Algorithms, ESA 2008, September 2008, pp. 368\u2013380","DOI":"10.1007\/978-3-540-87744-8_31"},{"key":"9348_CR13","doi-asserted-by":"crossref","unstructured":"Fiat, A., Kaplan, H., Levy, M., Olonetsky, S.: Strong price of anarchy for machine load balancing. In Proc. of the 34th International Colloquium on Automata, Languages and Programming, ICALP 2007, pp. 583\u2013594 (2007)","DOI":"10.1007\/978-3-540-73420-8_51"},{"key":"9348_CR14","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Kontogiannis, S.C., Koutsoupias, E., Mavronicolas, M., Spirakis, P.G.: The structure and complexity of Nash equilibria for a selfish routing game. In: Proc. of the 29th International Colloquium on Automata, Languages and Programming, ICALP 2002, pp. 123\u2013134 (2002)","DOI":"10.1007\/3-540-45465-9_12"},{"key":"9348_CR15","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Kontogiannis, S.C., Spirakis, P.G.: Atomic congestion games among coalitions. In: Proc. of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, Part I, pp. 572\u2013583 (2006)","DOI":"10.1007\/11786986_50"},{"key":"9348_CR16","doi-asserted-by":"crossref","unstructured":"Graham, R.L.: Bounds on multiprocessing anomalies and related packing algorithms. In: Proceedings of the 1972 Spring Joint Computer Conference, pp. 205\u2013217 (1972)","DOI":"10.1145\/1478873.1478901"},{"key":"9348_CR17","doi-asserted-by":"crossref","unstructured":"Hayrapetyan, A., Tardos, \u00c9., Wexler, T.: The effect of collusion in congestion games. In: Proc. of the 38th Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 89\u201398 (2006)","DOI":"10.1145\/1132516.1132529"},{"issue":"1\u20132","key":"9348_CR18","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/game.1997.0592","volume":"2","author":"R. Holzman","year":"1997","unstructured":"Holzman, R., Law-Yone, N.: Strong equilibrium in congestion games. Games Econ. Behav. 2(1\u20132), 85\u2013101 (1997)","journal-title":"Games Econ. Behav."},{"key":"9348_CR19","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Koutsoupias, E., Papadimitriou, C.H., Shenker, S.: Optimization problems in congestion control. In: Proc. of the 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, pp. 66\u201374 (2000)","DOI":"10.1109\/SFCS.2000.892066"},{"key":"9348_CR20","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: Proc. of the 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999, pp. 404\u2013413 (1999)","DOI":"10.1007\/3-540-49116-3_38"},{"issue":"6","key":"9348_CR21","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1007\/s00224-003-1131-5","volume":"36","author":"E. Koutsoupias","year":"2003","unstructured":"Koutsoupias, E., Mavronicolas, M., Spirakis, P.G.: Approximate equilibria and ball fusion. Theory Comput. Syst. 36(6), 683\u2013693 (2003)","journal-title":"Theory Comput. Syst."},{"key":"9348_CR22","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"C.C. Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple online bin packing algorithm. J. ACM 32, 562\u2013572 (1985)","journal-title":"J. ACM"},{"key":"9348_CR23","doi-asserted-by":"crossref","unstructured":"L\u00fccking, T., Mavronicolas, M., Monien, B., Rode, M.: A new model for selfish routing. In: Proc. of the 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004, pp. 547\u2013558 (2004)","DOI":"10.1007\/978-3-540-24749-4_48"},{"key":"9348_CR24","doi-asserted-by":"crossref","unstructured":"Mavronicolas, M., Spirakis, P.G.: The price of selfish routing. In: Proc. of the 33rd Annual Symposium on Theory of Computing, STOC 2001, pp. 510\u2013519 (2001)","DOI":"10.1145\/380752.380846"},{"issue":"2","key":"9348_CR25","doi-asserted-by":"crossref","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"9348_CR26","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Algorithms, games, and the Internet. In: Proc. of the 33rd Annual Symposium on Theory of Computing, STOC 2001, pp. 749\u2013753 (2001)","DOI":"10.1145\/380752.380883"},{"key":"9348_CR27","doi-asserted-by":"crossref","unstructured":"Roughgarden, T.: Designing networks for selfish users is hard. In: Proc. of the 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, pp. 472\u2013481 (2001)","DOI":"10.1109\/SFCS.2001.959923"},{"key":"9348_CR28","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., \u00c9., Tardos.: How bad is selfish routing? In: Proc. of the 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, pp. 93\u2013102 (2000)","DOI":"10.1109\/SFCS.2000.892069"},{"key":"9348_CR29","doi-asserted-by":"crossref","unstructured":"Tennenholtz, M., Rozenfeld, O.: Strong and correlated strong equilibria in monotone congestion games. In: Proc. of the 2nd International Workshop on Internet and Network Economics, WINE 2006, pp. 74\u201386 (2006)","DOI":"10.1007\/11944874_8"},{"key":"9348_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-0531(87)90099-8","volume":"42","author":"M. Whinston","year":"1987","unstructured":"Whinston, M., Bernheim, B., Peleg, B.: Coalition-proof Nash equilibria: I concepts. J. Econ. Theory 42, 1\u201312 (1987)","journal-title":"J. Econ. Theory"},{"issue":"5","key":"9348_CR31","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1109\/90.879352","volume":"8","author":"H. Ya\u00efche","year":"2000","unstructured":"Ya\u00efche, H., Mazumdar, R., Rosenberg, C.: A game theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE\/ACM Trans. Netw. 8(5), 667\u2013678 (2000)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"9348_CR32","doi-asserted-by":"crossref","unstructured":"Yu, G., Zhang, G.: Bin packing of selfish items. In: Proc. of the 4th International Workshop on Internet and Network Economics, WINE 2008, December 2008, pp. 446\u2013453","DOI":"10.1007\/978-3-540-92185-1_50"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9348-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9348-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9348-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T18:41:53Z","timestamp":1739299313000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9348-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,13]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["9348"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9348-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,13]]}}}