{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T08:26:15Z","timestamp":1774599975924,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Singapore Ministry of Education Academic Research Fund Tier 1","award":["RG112\/19"],"award-info":[{"award-number":["RG112\/19"]}]},{"name":"Singapore Ministry of Education Academic Research Fund Tier 2","award":["MOE-T2EP20121-0005"],"award-info":[{"award-number":["MOE-T2EP20121-0005"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>The MinUsageTime Dynamic Bin Packing (DBP) problem aims to minimize the accumulated bin usage time for packing a sequence of items into bins. It is often used to model job dispatching for optimizing the busy time of servers, where the items and bins match the jobs and servers respectively. It is known that the competitiveness of MinUsageTime DBP has tight bounds of \u0398(\u221a\u0142og \u03bc ) and \u0398(\u03bc) in the clairvoyant and non-clairvoyant settings respectively, where \u03bc is the max\/min duration ratio of all items. In practice, the information about the items' durations (i.e., job lengths) obtained via predictions is usually prone to errors. In this paper, we study the MinUsageTime DBP problem with predictions of the items' durations. We find that an existing O(\u221a\u0142og \u03bc )-competitive clairvoyant algorithm, if using predicted durations rather than real durations for packing, does not provide any bounded performance guarantee when the predictions are adversarially bad. We develop a new online algorithm with a competitive ratio of min\u00d8(\u03b5^2 \u221a\u0142og(\u03b5^2 \u03bc) ), O(\u03bc) (where \u03b5 is the maximum multiplicative error of prediction among all items), achieving O(\u221a\u0142og \u03bc) consistency (competitiveness under perfect predictions where \u03b5 = 1) and O(\u03bc) robustness (competitiveness under terrible predictions), both of which are asymptotically optimal.<\/jats:p>","DOI":"10.1145\/3570605","type":"journal-article","created":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T20:20:10Z","timestamp":1670530810000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Dynamic Bin Packing with Predictions"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6181-9958","authenticated-orcid":false,"given":"Mozhengfu","family":"Liu","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]},{"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":[[2022,12,8]]},"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. 2021. Amazon EC2. http:\/\/aws.amazon.com\/ec2\/  Amazon. 2021. 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":"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 . Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Vol. 53. Cambridge University Press Cambridge."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3410220.3456278"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-017-0531-3"},{"key":"e_1_2_1_9_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. 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_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212014"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.011"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning. 2319--2327","author":"Gollapudi Sreenivas","year":"2019","unstructured":"Sreenivas Gollapudi and Debmalya Panigrahi . 2019 . Online algorithms for rent-or-buy with expert advice . In Proceedings of the 36th International Conference on Machine Learning. 2319--2327 . Sreenivas Gollapudi and Debmalya Panigrahi. 2019. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning. 2319--2327."},{"key":"e_1_2_1_13_1","unstructured":"Google. 2021. Google Cloud. https:\/\/cloud.google.com\/  Google. 2021. Google Cloud. https:\/\/cloud.google.com\/"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461790"},{"key":"e_1_2_1_15_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 . 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_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-014-0411-z"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_44"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 32nd Conference on Neural Information Processing Systems. 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. 9661--9670 . 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. 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","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 . 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_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.033"},{"key":"e_1_2_1_27_1","unstructured":"Microsoft. 2021. Microsoft Azure. https:\/\/azure.microsoft.com\/  Microsoft. 2021. Microsoft Azure. https:\/\/azure.microsoft.com\/"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935775"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087562"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS47924.2020.00040"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2016.2630052"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3002786"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.112"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.07.017"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1551609.1551632"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2889712"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.42"},{"key":"e_1_2_1_38_1","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V","unstructured":"Vijay V Vazirani . 2013. Approximation Algorithms . Springer Science & Business Media . Vijay V Vazirani. 2013. Approximation Algorithms. Springer Science & Business Media."},{"key":"e_1_2_1_39_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 . 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_40_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 . io 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. io"}],"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\/3570605","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:17Z","timestamp":1750178777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1145\/3570605"],"URL":"https:\/\/doi.org\/10.1145\/3570605","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2022-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}