{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T03:38:39Z","timestamp":1775533119808,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education, Singapore","doi-asserted-by":"crossref","award":["MOE-T2EP20122-0007"],"award-info":[{"award-number":["MOE-T2EP20122-0007"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]}],"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            MinUsageTime DBP is a variant of the Dynamic Bin Packing (DBP) problem that seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This DBP variant models job dispatching for optimizing the busy time of machines, which finds applications in cloud computing and energy-efficient computing. This paper studies the MinUsageTime DBP problem with predictions about item durations (job lengths). We establish tight competitiveness bounds over the entire spectrum of prediction errors. First, we give a lower bound \u03a9(min {max{\u03b5 \u22c5 \u221a log \u03bc, \u03b5\n            <jats:sup>2<\/jats:sup>\n            }, \u03bc}) on the competitive ratio of any deterministic online algorithm, where \u03bc is the max\/min duration ratio of all items and \u03b5 is the maximum multiplicative prediction error. Then, we show that the competitive ratio of a recent algorithm has strictly higher asymptotic order than the above lower bound when \u03b5 = \u03c9(1) \u2227 \u03b5 = o(\u221a \u03bc). Finally, we present an enhanced algorithm and prove that it achieves a competitive ratio matching the above lower bound, closing the gap for this problem.\n          <\/jats:p>","DOI":"10.1145\/3700437","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":1,"title":["Tight Bounds for Dynamic Bin Packing with Predictions"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6181-9958","authenticated-orcid":false,"given":"Mozhengfu","family":"Liu","sequence":"first","affiliation":[{"name":"Northwestern University, Evanston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7404-7595","authenticated-orcid":false,"given":"Xueyan","family":"Tang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2024,12,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_5"},{"key":"e_1_2_1_2_1","unstructured":"Amazon. 2023. Amazon EC2. http:\/\/aws.amazon.com\/ec2\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2022\/635"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087570"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364214"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 6th Conference on Machine Learning and Systems (MLSys).","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, Tamires Santos, Larissa Rozales Gon\u00e7alves, David Dion, Thomas Moscibroda, and Ishai Menache. 2023. Virtual Machine Allocation with Lifetime Predictions. In Proceedings of the 6th Conference on Machine Learning and Systems (MLSys)."},{"key":"e_1_2_1_7_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","unstructured":"Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Vol. 53. Cambridge University Press Cambridge."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3410220.3456278"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-017-0531-3"},{"key":"e_1_2_1_10_1","volume-title":"Bin Packing Approximation Algorithms: Survey and Classification. Handbook of Combinatorial Optimization","author":"Coffman Edward G.","year":"2013","unstructured":"Edward G. Coffman Jr, J\u00e1nos Csirik, G\u00e1bor Galambos, Silvano Martello, and Daniele Vigo. 2013. Bin Packing Approximation Algorithms: Survey and Classification. Handbook of Combinatorial Optimization (second ed.) (2013), 455--531."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.011"},{"key":"e_1_2_1_13_1","unstructured":"Google. 2023. Google Cloud. https:\/\/cloud.google.com\/"},{"key":"e_1_2_1_14_1","volume-title":"Efficient Online Strategies for Renting Servers in the Cloud. In SOFSEM 2015: Theory and Practice of Computer Science. Springer, 277--288","author":"Kamali Shahin","year":"2015","unstructured":"Shahin Kamali and Alejandro L\u00f3pez-Ortiz. 2015. Efficient Online Strategies for Renting Servers in the Cloud. In SOFSEM 2015: Theory and Practice of Computer Science. Springer, 277--288."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-014-0411-z"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_44"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS). 9661--9670","author":"Kumar Ravi","year":"2018","unstructured":"Ravi Kumar, Manish Purohit, and Zoya Svitkina. 2018. Improving online algorithms via ML predictions. In Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS). 9661--9670."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612675"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSVT.2015.2450152"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2393868"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461795"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2022.3176665"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570605"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3660271"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML). 3302--3311","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvitskii. 2018. Competitive Caching with Machine Learned Advice. In Proceedings of the 35th International Conference on Machine Learning (ICML). 3302--3311."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 10th IEEE\/ACM International Conference on Cluster, Cloud and Grid Computing (CCGrid). 495--504","author":"Matsunaga Andr\u00e9a","unstructured":"Andr\u00e9a Matsunaga and Jos\u00e9 A. B. Fortes. 2010. On the Use of Machine Learning to Predict the Time and Resources Consumed by Applications. In Proceedings of the 10th IEEE\/ACM International Conference on Cluster, Cloud and Grid Computing (CCGrid). 495--504."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.033"},{"key":"e_1_2_1_30_1","unstructured":"Microsoft. 2023. Microsoft Azure. https:\/\/azure.microsoft.com\/"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935775"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087562"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS47924.2020.00040"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2016.2630052"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3002786"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.07.017"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1551609.1551632"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2889712"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.42"},{"key":"e_1_2_1_40_1","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V","unstructured":"Vijay V Vazirani. 2013. Approximation Algorithms. Springer Science & Business Media."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 13th USENIX Conference on Networked Systems Design and Implementation (NSDI). 363--378","author":"Venkataraman Shivaram","year":"2016","unstructured":"Shivaram Venkataraman, Zongheng Yang, Michael Franklin, Benjamin Recht, and Ion Stoica. 2016. Ernest: Efficient Performance Prediction for Large-Scale Advanced Analytics. In Proceedings of the 13th USENIX Conference on Networked Systems Design and Implementation (NSDI). 363--378."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 830--831","author":"Winkler Peter","year":"2003","unstructured":"Peter Winkler and Lisa Zhang. 2003. Wavelength Assignment and Generalized Interval Graph Coloring. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 830--831."}],"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\/3700437","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700437","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:13:22Z","timestamp":1755908002000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700437"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,10]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,12,10]]}},"alternative-id":["10.1145\/3700437"],"URL":"https:\/\/doi.org\/10.1145\/3700437","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"}}]}}