{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T08:26:11Z","timestamp":1774599971739,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T00:00:00Z","timestamp":1734048000000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ONR","award":["N000142212702"],"award-info":[{"award-number":["N000142212702"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2024,12,10]]},"abstract":"<jats:p>\n            In the\n            <jats:italic toggle=\"yes\">Dynamic Bin Packing<\/jats:italic>\n            problem,\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            items arrive and depart the system in an online manner, and the goal is to maintain a good packing throughout. We consider the objective of minimizing the total active time, i.e., the sum of the number of open bins over all times. An important tool for maintaining an efficient packing in many applications is the use of\n            <jats:italic toggle=\"yes\">migrations<\/jats:italic>\n            ; e.g., transferring computing jobs across different machines. However, there are large gaps in our understanding of the approximability of dynamic bin packing with migrations. Prior work has covered the power of no migrations and &gt; n migrations, but we ask the question: What is the power of limited (\u2264 n) migrations?\n          <\/jats:p>\n          <jats:p>\n            Our first result is a dichotomy between no migrations and linear migrations: Using a sublinear number of migrations is asymptotically equivalent to doing\n            <jats:italic toggle=\"yes\">zero<\/jats:italic>\n            migrations, where the competitive ratio grows with \u03bc, the ratio of the largest to smallest item duration. On the other hand, we prove that for every \u03b1 \u2208 (0,1], there is an algorithm that does \u2248 \u03b1 n migrations and achieves competitive ratio \u2248 1\/\u03b1 (in particular, independent of \u03bc); we also show that this tradeoff is essentially best possible. This fills in the gap between zero migrations and &gt; n migrations in Dynamic Bin Packing.\n          <\/jats:p>\n          <jats:p>\n            Finally, in light of the above impossibility results, we introduce a new model that more directly captures the impact of migrations. Instead of limiting the number of migrations, each migration adds a delay of\n            <jats:italic toggle=\"yes\">C<\/jats:italic>\n            time units to the item's duration; this commonly appears in settings where a blackout or set-up time is required before the item can restart its execution in the new bin. In this new model, we prove a O(min(\u221aC, \u03bc))-approximation, and an almost matching lower bound. We also present preliminary experiments that indicate that our theoretical results are predictive of the practical performance of our algorithms.\n          <\/jats:p>","DOI":"10.1145\/3700435","type":"journal-article","created":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T12:12:12Z","timestamp":1734091932000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Power of Migrations in Dynamic Bin Packing"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9245-8956","authenticated-orcid":false,"given":"Konstantina","family":"Mellou","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0174-3204","authenticated-orcid":false,"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[{"name":"Microsoft Research &amp; PUC-Rio, Rio, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5037-4885","authenticated-orcid":false,"given":"Rudy","family":"Zhou","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,13]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Azure trace for packing 2020. https:\/\/github.com\/Azure\/AzurePublicDataset year=2024."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0209--9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364214"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2018.5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18318-8_3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-008-0023--6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/050647049"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-012--9489--4"},{"key":"e_1_2_1_9_1","volume-title":"A new minimax theorem for randomized algorithms. CoRR, abs\/2002.10802","author":"Ben-David Shalev","year":"2020","unstructured":"Shalev Ben-David and Eric Blais. A new minimax theorem for randomized algorithms. CoRR, abs\/2002.10802, 2020. URL: https:\/\/arxiv.org\/abs\/2002.10802, arXiv:2002.10802."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00045"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018--1325-x"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/21m1428649"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3410220.3456278"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212014"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4419--7997--1_35"},{"key":"e_1_2_1_16_1","first-page":"3250","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Cohen-Addad Vincent","year":"2019","unstructured":"Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8--14, 2019, Vancouver, BC, Canada, pages 3250--3260, 2019. URL: https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/fface8385abbf94b4593a0ed53a0c70f-Abstract.html."},{"key":"e_1_2_1_17_1","volume-title":"On the sum-of-squares algorithm for bin packing. Journal of the ACM (JACM), 53(1):1--65","author":"Csirik Janos","year":"2006","unstructured":"Janos Csirik, David S Johnson, Claire Kenyon, James B Orlin, PeterWShor, and Richard RWeber. On the sum-of-squares algorithm for bin packing. Journal of the ACM (JACM), 53(1):1--65, 2006."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0200-y"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.48550\/arX"},{"key":"e_1_2_1_21_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP 2018","author":"Feldkord Bj\u00f6rn","year":"2018","unstructured":"Bj\u00f6rn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, S\u00f6ren Riechers, and David Wajc. Fully-dynamic bin packing with little repacking. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799180408"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","unstructured":"Xiangyu Guo Janardhan Kulkarni Shi Li and Jiayi Xian. On the facility location problem in online and dynamic models. In Jaroslaw Byrka and Raghu Meka editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM 2020 August 17--19 2020 Virtual Conference volume 176 of LIPIcs pages 42:1--42:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 2020. URL: https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RA NDOM.2020.42 doi:10.4230\/LIPICS.APPROX\/RANDOM.2020.42.","DOI":"10.4230\/LIPIcs.APPROX\/RA"},{"key":"e_1_2_1_24_1","series-title":"Proceedings of Machine Learning Research","first-page":"1135","volume-title":"The 24th International Conference on Artificial Intelligence and Statistics, AISTATS","author":"Guo Xiangyu","year":"2021","unstructured":"Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. Consistent k-median: Simpler, better and robust. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13--15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 1135--1143. PMLR, 2021. URL: http:\/\/proceedings.mlr.press\/v130\/guo21a.html."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.57"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055493"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.34"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00110"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2023.65"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1914"},{"key":"e_1_2_1_31_1","first-page":"845","volume-title":"14th USENIX Symposium 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, et al. Protean:{VM} allocation service at scale. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 845--861, 2020."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2311.17038"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.172"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794276749"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00112--3"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1122529"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212014"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585222"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746615"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612675"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2393868"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570605"},{"key":"e_1_2_1_44_1","volume-title":"Online bin packing with known T. arXiv preprint arXiv:2112.03200","author":"Liu Shang","year":"2021","unstructured":"Shang Liu and Xiaocheng Li. Online bin packing with known T. arXiv preprint arXiv:2112.03200, 2021."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935775"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222074"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3296975.3186415"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0381"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585269"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1--4613--3557--3_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2013.148"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.42"},{"key":"e_1_2_1_53_1","first-page":"44","volume-title":"Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee","author":"Wong Prudence W. H.","year":"2012","unstructured":"Prudence W. H. Wong, Fencol C. C. Yung, and Mihai Burcea. An 8\/3 lower bound for online dynamic bin packing. In Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee, editors, Algorithms and Computation, pages 44--53, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700435","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700435","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700435","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:13:42Z","timestamp":1755908022000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700435"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,10]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,12,10]]}},"alternative-id":["10.1145\/3700435"],"URL":"https:\/\/doi.org\/10.1145\/3700435","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,10]]},"assertion":[{"value":"2024-12-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}