{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T03:06:32Z","timestamp":1785207992418,"version":"3.55.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"National Science Foundation","award":["2045641"],"award-info":[{"award-number":["2045641"]}]},{"name":"National Science Foundation","award":["2325956"],"award-info":[{"award-number":["2325956"]}]},{"name":"National Science Foundation","award":["2512128"],"award-info":[{"award-number":["2512128"]}]},{"name":"National Science Foundation","award":["2533814"],"award-info":[{"award-number":["2533814"]}]},{"name":"Natural Sciences and Engineering Research Council of Canada","award":["RGPIN-2025-07295"],"award-info":[{"award-number":["RGPIN-2025-07295"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2026,3,26]]},"abstract":"<jats:p>\n                    The online bin packing problem and its variants are regularly used to model server allocation problems. Modern concerns surrounding sustainability and overcommitment in cloud computing motivate bin packing models that capture costs associated with highly utilized servers. In this work, we introduce the\n                    <jats:italic toggle=\"yes\">green bin packing<\/jats:italic>\n                    problem, an online variant with a linear cost \u03b2 for filling above a fixed level\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    . For a given instance, the goal is to minimize the sum of the number of opened bins and the linear cost. We show that when \u03b2 \u2264 1\/\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    , classical online bin packing algorithms such as FirstFit or Harmonic perform well, and can achieve competitive ratios lower than in the classic setting. However, when \u03b2 &gt; 1\/\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    , new algorithmic solutions can improve both worst-case and typical performance. We introduce variants of classic online bin packing algorithms and establish theoretical bounds, as well as test their empirical performance.\n                  <\/jats:p>","DOI":"10.1145\/3788093","type":"journal-article","created":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:49:47Z","timestamp":1774550987000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Green Bin Packing"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-5063-0700","authenticated-orcid":false,"given":"Jackson","family":"Bibbens","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4720-3626","authenticated-orcid":false,"given":"Cooper","family":"Sigrist","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3172-7811","authenticated-orcid":false,"given":"Bo","family":"Sun","sequence":"additional","affiliation":[{"name":"University of Ottawa, Ottawa, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1404-2212","authenticated-orcid":false,"given":"Shahin","family":"Kamali","sequence":"additional","affiliation":[{"name":"York University, Toronto, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9278-2254","authenticated-orcid":false,"given":"Mohammad","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2022\/635"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2018.5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-012-9489-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.06.045"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.04.017"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3393691.3394224"},{"key":"e_1_2_1_7_1","first-page":"232","article-title":"Virtual machine allocation with lifetime predictions","volume":"5","author":"Barbalho Hugo","year":"2023","unstructured":"Hugo Barbalho, Patricia Kovaleski, Beibin Li, Luke Marshall, Marco Molinaro, Abhisek Pan, Eli Cortez, Matheus Leao, Harsh Patwari, Zuzu Tang, et al., 2023. Virtual machine allocation with lifetime predictions. Proceedings of Machine Learning and Systems, Vol. 5 (2023), 232-253.","journal-title":"Proceedings of Machine Learning and Systems"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Sixteenth European Conference on Computer Systems. 556-573","author":"Bashir Noman","year":"2021","unstructured":"Noman Bashir, Nan Deng, Krzysztof Rzadca, David Irwin, Sree Kodak, and Rohit Jnagal. 2021. Take it to the limit: peak prediction-driven resource overcommitment in datacenters. In Proceedings of the Sixteenth European Conference on Computer Systems. 556-573."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808692"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-020-00695-5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33558-7_17"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-006-5594-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2018.3091"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132772"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120583"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0791"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579456"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799180408"},{"key":"e_1_2_1_19_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626334"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2015.0670"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1914"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI'20)","author":"Hadary Ori","year":"2020","unstructured":"Ori Hadary, Luke Marshall, Ishai Menache, Abhisek Pan, Esaias E Greeff, David Dion, Star Dorminey, Shailesh Joshi, Yang Chen, Mark Russinovich, and Thomas Moscibroda. 2020. Protean: VM allocation service at scale. In Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI'20). USENIX Association, USA, Article 48, 17 pages."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725980"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626779"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"David Irwin Prashant Shenoy Mohammad Hajiesmaili Walid A Hanafy Jimi Oke Ramesh Sitaraman Yuvraj Agarwal Geoff Gordon Zico Kolter Deepak Rajagopal et al. 2025. A Vision for Computational Decarbonization of Societal Infrastructure. IEEE Internet Computing (2025).","DOI":"10.1109\/MIC.2025.3575016"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1122529"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_49"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"e_1_2_1_30_1","volume-title":"Efficient Bin Packing Algorithms for Resource Provisioning in the Cloud. In International Workshop on Algorithmic Aspects of Cloud Computing. https:\/\/api.semanticscholar.org\/CorpusID:10608206","author":"Kamali Shahin","year":"2015","unstructured":"Shahin Kamali. 2015. Efficient Bin Packing Algorithms for Resource Provisioning in the Cloud. In International Workshop on Algorithmic Aspects of Cloud Computing. https:\/\/api.semanticscholar.org\/CorpusID:10608206"},{"key":"e_1_2_1_31_1","first-page":"727","volume-title":"Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC)","volume":"9472","author":"Kamali Shahin","year":"2015","unstructured":"Shahin Kamali and Alejandro L\u00f3pez-Ortiz. 2015. An all-around near-optimal solution for the classic bin packing problem. Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), Vol. 9472 (2015), 727-739."},{"key":"e_1_2_1_32_1","volume-title":"Algorithmic Aspects of Cloud Computing, Gianlorenzo D'Angelo and Othon Michail (Eds.)","author":"Kamali Shahin","unstructured":"Shahin Kamali and Pooya Nikbakht. 2021. On the Fault-Tolerant Online Bin Packing Problem. In Algorithmic Aspects of Cloud Computing, Gianlorenzo D'Angelo and Othon Michail (Eds.). Springer International Publishing, Cham, 1-17."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808693"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.215.0443"},{"key":"e_1_2_1_35_1","first-page":"473","volume-title":"2021 USENIX Annual Technical Conference (USENIX ATC 21)","author":"Kumbhare Alok Gautam","year":"2021","unstructured":"Alok Gautam Kumbhare, Reza Azimi, Ioannis Manousakis, Anand Bonde, Felipe Frujeri, Nithish Mahalingam, Pulkit A Misra, Seyyed Ahmad Javadi, Bianca Schroeder, Marcus Fontoura, et al., 2021. {Prediction-Based} power oversubscription in cloud platforms. In 2021 USENIX Annual Technical Conference (USENIX ATC 21). 473-487."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3711701"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3833"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00895-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","first-page":"498","DOI":"10.2307\/2273574","article-title":"Michael R. Garey and David S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. WH Freeman and Company, San Francisco1979, x+ 338 pp","volume":"48","author":"Lewis Harry R","year":"1983","unstructured":"Harry R Lewis. 1983. Michael R. Garey and David S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. WH Freeman and Company, San Francisco1979, x+ 338 pp. The Journal of Symbolic Logic, Vol. 48, 2 (1983), 498-500.","journal-title":"The Journal of Symbolic Logic"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(80)90077-0"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/IGCC.2012.6322266"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCC.2022.3150391"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570605"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2007116.2007139"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-017-1192-z"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3700435"},{"key":"e_1_2_1_47_1","volume-title":"Looking Beyond GPUs for DNN Scheduling on Multi-Tenant Clusters. In USENIX Symposium on Operating Systems Design and Implementation (OSDI","author":"Mohan Jayashree","year":"2022","unstructured":"Jayashree Mohan, Amar Phanishayee, Janardhan (Jana) Kulkarni, and Vijay Chidambaram. 2022. Looking Beyond GPUs for DNN Scheduling on Multi-Tenant Clusters. In USENIX Symposium on Operating Systems Design and Implementation (OSDI 2022). https:\/\/www.microsoft.com\/en-us\/research\/publication\/synergy-looking-beyond-gpus-for-dnn-scheduling-on-multi-tenant-clusters\/"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698038.3698516"},{"key":"e_1_2_1_49_1","volume-title":"Heuristics for Vector Bin Packing. (January","author":"Panigrahy Rina","year":"2011","unstructured":"Rina Panigrahy, Kunal Talwar, Lincoln Uyeda, and Udi Wieder. 2011. Heuristics for Vector Bin Packing. (January 2011). https:\/\/www.microsoft.com\/en-us\/research\/publication\/heuristics-for-vector-bin-packing\/"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1239"},{"key":"e_1_2_1_51_1","first-page":"164","volume-title":"Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems","volume":"1","author":"Reidys Benjamin","year":"2025","unstructured":"Benjamin Reidys, Pantea Zardoshti, \u00cd\u00f1igo Goiri, Celine Irvene, Daniel S Berger, Haoran Ma, Kapil Arya, Eli Cortez, Taylor Stark, Eugene Bak, et al., 2025. Coach: Exploiting temporal patterns for all-resource oversubscription in cloud platforms. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1. 164-181."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222074"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2013.148"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627703.3650079"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.2307\/2369261"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90223-I"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322187"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3788093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:53:11Z","timestamp":1774551191000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3788093"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,26]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,26]]}},"alternative-id":["10.1145\/3788093"],"URL":"https:\/\/doi.org\/10.1145\/3788093","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,26]]},"assertion":[{"value":"2026-03-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}