{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T20:13:01Z","timestamp":1773778381390,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s00453-021-00849-0","type":"journal-article","created":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T18:04:43Z","timestamp":1625162683000},"page":"2952-2988","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Selfish Vector Packing"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6761-8521","authenticated-orcid":false,"given":"Leah","family":"Epstein","sequence":"first","affiliation":[]},{"given":"Elena","family":"Kleiman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,1]]},"reference":[{"issue":"2","key":"849_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.geb.2008.03.005","volume":"65","author":"N Andelman","year":"2009","unstructured":"Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. Games Econ. Behav. 65(2), 289\u2013317 (2009)","journal-title":"Games Econ. Behav."},{"issue":"4","key":"849_CR2","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/070680096","volume":"38","author":"E Anshelevich","year":"2008","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. SIAM J. Comput. 38(4), 1602\u20131623 (2008)","journal-title":"SIAM J. Comput."},{"key":"849_CR3","first-page":"287","volume-title":"Contributions to the Theory of Games IV, Annals of Mathematics Study","author":"RJ 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":"849_CR4","doi-asserted-by":"crossref","unstructured":"Aumann, Y., Dombb, Y.: Pareto efficiency and approximate Pareto efficiency in routing and load balancing games. In: Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT2010), pp. 66\u201377 (2010)","DOI":"10.1007\/978-3-642-16170-4_7"},{"key":"849_CR5","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V.: On the packing of selfish items. In: Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS2006). IEEE (2006)","DOI":"10.1109\/IPDPS.2006.1639283"},{"issue":"4","key":"849_CR6","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1137\/S0097539799356265","volume":"33","author":"C Chekuri","year":"2004","unstructured":"Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM J. Comput. 33(4), 837\u2013851 (2004)","journal-title":"SIAM J. Comput."},{"key":"849_CR7","doi-asserted-by":"crossref","unstructured":"Chien, S., Sinclair, A.: Strong and Pareto price of anarchy in congestion games. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP2009), pp. 279\u2013291 (2009)","DOI":"10.1007\/978-3-642-02927-1_24"},{"key":"849_CR8","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-1-4419-7997-1_35","volume-title":"Handbook of Combinatorial Optimization","author":"EG Coffman Jr","year":"2013","unstructured":"Coffman, E.G., Jr., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: survey and classification. In: Pardalos, P.M., Du, D.Z., Graham, R.L.L. (eds.) Handbook of Combinatorial Optimization, pp. 455\u2013531. Springer, New York (2013)"},{"key":"849_CR9","unstructured":"D\u00f3sa, G., Epstein, L.: Generalized selfish bin packing (2012). CoRR, arXiv:1202.4080"},{"issue":"3","key":"849_CR10","doi-asserted-by":"publisher","first-page":"853","DOI":"10.14232\/actacyb.23.3.2018.8","volume":"23","author":"G D\u00f3sa","year":"2018","unstructured":"D\u00f3sa, G., Epstein, L.: The convergence time for selfish bin packing. Acta Cybern. 23(3), 853\u2013865 (2018)","journal-title":"Acta Cybern."},{"key":"849_CR11","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.ipl.2019.06.002","volume":"150","author":"G D\u00f3sa","year":"2019","unstructured":"D\u00f3sa, G., Epstein, L.: A new lower bound on the price of anarchy of selfish bin packing. Inf. Process. Lett. 150, 6\u201312 (2019)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"849_CR12","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1007\/s10878-018-0323-5","volume":"37","author":"G D\u00f3sa","year":"2019","unstructured":"D\u00f3sa, G., Epstein, L.: Pareto optimal equilibria for selfish bin packing with uniform cost sharing. J. Comb. Optim. 37(3), 827\u2013847 (2019)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"849_CR13","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s10951-018-0587-8","volume":"22","author":"G D\u00f3sa","year":"2019","unstructured":"D\u00f3sa, G., Epstein, L.: Quality of strong equilibria for selfish bin packing with uniform cost sharing. J. Sched. 22(4), 473\u2013485 (2019)","journal-title":"J. Sched."},{"key":"849_CR14","doi-asserted-by":"publisher","first-page":"100556","DOI":"10.1016\/j.disopt.2019.100556","volume":"38","author":"G D\u00f3sa","year":"2020","unstructured":"D\u00f3sa, G., Epstein, L.: Quality of equilibria for selfish bin packing with cost sharing variants. Discrete Optim. 38, 100556 (2020)","journal-title":"Discrete Optim."},{"issue":"1","key":"849_CR15","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/j.ejor.2019.04.026","volume":"278","author":"G D\u00f3sa","year":"2019","unstructured":"D\u00f3sa, G., Kellerer, H., Tuza, Z.: Using weight decision for decreasing the price of anarchy in selfish bin packing games. Eur. J. Oper. Res. 278(1), 160\u2013169 (2019)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"849_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.11.1.1","volume":"11","author":"P Dubey","year":"1986","unstructured":"Dubey, P.: Inefficiency of Nash equilibria. Math. Oper. Res. 11(1), 1\u20138 (1986)","journal-title":"Math. Oper. Res."},{"key":"849_CR17","doi-asserted-by":"crossref","unstructured":"Epstein, L., Kleiman, E.: Selfish bin packing. In: Proceedings of the 16th Annual European Symposium (ESA2008), pp. 368\u2013380 (2008)","DOI":"10.1007\/978-3-540-87744-8_31"},{"key":"849_CR18","unstructured":"Epstein, L., Kleiman, E.: On the quality and complexity of Pareto equilibria in the job scheduling game. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS2011), pp. 525\u2013532 (2011)"},{"issue":"2","key":"849_CR19","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/s00453-009-9348-6","volume":"60","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Kleiman, E.: Selfish bin packing. Algorithmica 60(2), 368\u2013394 (2011)","journal-title":"Algorithmica"},{"key":"849_CR20","doi-asserted-by":"crossref","unstructured":"Epstein, L., Kleiman, E.: Selfish vector packing. In: Proceedinngs of the 23rd Annual European Symposium on Algorithms (ESA2015), pp. 471\u2013482 (2015)","DOI":"10.1007\/978-3-662-48350-3_40"},{"issue":"1","key":"849_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00453-014-9942-0","volume":"74","author":"L Epstein","year":"2016","unstructured":"Epstein, L., Kleiman, E., Mestre, J.: Parametric packing of selfish items and the Subset Sum algorithm. Algorithmica 74(1), 177\u2013207 (2016)","journal-title":"Algorithmica"},{"key":"849_CR22","doi-asserted-by":"crossref","unstructured":"Fiat, A., Kaplan, H., Levy, M., Olonetsky, S.: Strong price of anarchy for machine load balancing. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP2007), pp. 583\u2013594 (2007)","DOI":"10.1007\/978-3-540-73420-8_51"},{"issue":"3","key":"849_CR23","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","volume":"21","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Resource constrained scheduling as generalized bin packing. J. Comb. Theory Ser. A 21(3), 257\u2013298 (1976)","journal-title":"J. Comb. Theory Ser. A"},{"key":"849_CR24","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)"},{"issue":"1\u20132","key":"849_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1006\/game.1997.0592","volume":"21","author":"R Holzman","year":"1997","unstructured":"Holzman, R., Law-Yone, N.: Strong equilibrium in congestion games. Games Econ. Behav. 21(1\u20132), 85\u2013101 (1997)","journal-title":"Games Econ. Behav."},{"key":"849_CR26","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 256\u2013278 (1974)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"849_CR27","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1147\/rd.215.0443","volume":"21","author":"LT Kou","year":"1977","unstructured":"Kou, L.T., Markowsky, G.: Multidimensional bin packing algorithms. IBM J. Res. Dev. 21(5), 443\u2013448 (1977)","journal-title":"IBM J. Res. Dev."},{"key":"849_CR28","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.H. Worst-case equilibria. In: Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS1999), pp. 404\u2013413 (1999)","DOI":"10.1007\/3-540-49116-3_38"},{"key":"849_CR29","unstructured":"Lee, S., Panigrahy, R., Prabhakaran, V., Ramasubrahmanian, V., Talwar, K., Uyeda, L., Wieder, U.: Validating heuristics for virtual machine consolidation. In: Microsoft Research, MSR-TR-2011-9 (2011)"},{"key":"849_CR30","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-0-387-77247-9_18","volume-title":"Pareto Optimality, Game Theory and Equilibria","author":"DT Luc","year":"2008","unstructured":"Luc, D.T.: Pareto optimality. In: Chinchuluun, A., Pardalos, P.M., Migdalas, A., Pitsoulis, L. (eds.) Pareto Optimality, Game Theory and Equilibria, pp. 481\u2013515. Springer, Berlin (2008)"},{"issue":"4","key":"849_CR31","doi-asserted-by":"publisher","first-page":"1457","DOI":"10.1007\/s10898-012-9856-9","volume":"56","author":"R Ma","year":"2013","unstructured":"Ma, R., D\u00f3sa, G., Han, X., Ting, H.F., Ye, D., Zhang, Y.: A note on a selfish bin packing problem. J. Glob. Optim. 56(4), 1457\u20131462 (2013)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"849_CR32","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00453-006-0056-1","volume":"48","author":"M Mavronicolas","year":"2007","unstructured":"Mavronicolas, M., Spirakis, P.G.: The price of selfish routing. Algorithmica 48(1), 91\u2013126 (2007)","journal-title":"Algorithmica"},{"key":"849_CR33","doi-asserted-by":"crossref","unstructured":"Tennenholtz, M., Rozenfeld, O.: Strong and correlated strong equilibria in monotone congestion games. In: Proceedings of the 2nd International Workshop on Internet and Network Economics (WINE2006), pp. 74\u201386 (2006)","DOI":"10.1007\/11944874_8"},{"issue":"5","key":"849_CR34","doi-asserted-by":"publisher","first-page":"1534","DOI":"10.1007\/s00453-017-0361-x","volume":"80","author":"Z Wang","year":"2018","unstructured":"Wang, Z., Han, X., D\u00f3sa, G., Tuza, Z.: A general bin packing game: interest taken into account. Algorithmica 80(5), 1534\u20131555 (2018)","journal-title":"Algorithmica"},{"issue":"6","key":"849_CR35","doi-asserted-by":"publisher","first-page":"1345","DOI":"10.1016\/j.future.2013.02.004","volume":"29","author":"D Ye","year":"2013","unstructured":"Ye, D., Chen, J.: Non-cooperative games on multidimensional resource allocation. Future Gener. Comput. Syst. 29(6), 1345\u20131352 (2013)","journal-title":"Future Gener. Comput. Syst."},{"issue":"11","key":"849_CR36","first-page":"3021","volume":"9","author":"B Yin","year":"2012","unstructured":"Yin, B., Wang, Y., Meng, L., Qiu, X.: A multi-dimensional resource allocation algorithm in cloud computing. J. Inf. Comput. Sci. 9(11), 3021\u20133028 (2012)","journal-title":"J. Inf. Comput. Sci."},{"key":"849_CR37","doi-asserted-by":"crossref","unstructured":"Yu, G., Zhang, G.: Bin packing of selfish items. In: The 4th International Workshop on Internet and Network Economics (WINE2008), pp. 446\u2013453 (2008)","DOI":"10.1007\/978-3-540-92185-1_50"},{"issue":"1","key":"849_CR38","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/s13174-010-0007-6","volume":"1","author":"Q Zhang","year":"2010","unstructured":"Zhang, Q., Cheng, L., Boutaba, R.: Cloud computing: state-of-the-art and research challenges. J. Internet Serv. Appl. 1(1), 7\u201318 (2010)","journal-title":"J. Internet Serv. Appl."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00849-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00849-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00849-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T11:08:00Z","timestamp":1628161680000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00849-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,1]]},"references-count":38,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["849"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00849-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,1]]},"assertion":[{"value":"19 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}