{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:42:25Z","timestamp":1767339745976,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,9,30]],"date-time":"2019-09-30T00:00:00Z","timestamp":1569801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israeli Science Foundation","doi-asserted-by":"crossref","award":["1506\/16"],"award-info":[{"award-number":["1506\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"I-Core program","award":["center no. 4\/11"],"award-info":[{"award-number":["center no. 4\/11"]}]},{"name":"ICRC blatvatnik fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            In this article, we focus on the Clairvoyant Dynamic Bin Packing (DBP) problem, which extends the Classical Online Bin Packing problem in that items arrive and depart over time and the departure time of an item is known upon its arrival. The problem naturally arises when handling cloud-based networks. We focus specifically on the MinUsageTime objective function, which aims to minimize the overall usage time of all bins that are opened during the packing process. Earlier work has shown a\n            <jats:italic>O<\/jats:italic>\n            (log &amp;mu \/ log log \u03bc) upper bound on the algorithm\u2019s competitiveness, where \u03bc is defined as the ratio between the maximal and minimal durations of all items. We improve the upper bound by giving a\n            <jats:italic>O<\/jats:italic>\n            (\u221a log \u03bc)-competitive algorithm. We then provide a matching lower bound of \u03a9 (\u221a log \u03bc) on the competitive ratio of any online algorithm, thus closing the gap with regard to this problem. We then focus on what we call the class of aligned inputs and give a\n            <jats:italic>O<\/jats:italic>\n            (log log \u03bc)-competitive algorithm for this case, beating the lower bound of the general case by an exponential factor. Surprisingly enough, the analysis of our algorithm that we present is closely related to various properties of binary strings.\n          <\/jats:p>","DOI":"10.1145\/3364214","type":"journal-article","created":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T16:35:58Z","timestamp":1571157358000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Tight Bounds for Clairvoyant Dynamic Bin Packing"],"prefix":"10.1145","volume":"6","author":[{"given":"Yossi","family":"Azar","sequence":"first","affiliation":[{"name":"Tel-Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Vainstein","sequence":"additional","affiliation":[{"name":"Tel-Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"New lower bounds for certain classes of bin packing algorithms. Theor. Comput. Sci. 440--441","author":"Balogh J\u00e1nos","year":"2012","unstructured":"J\u00e1nos Balogh , J\u00f3zsef B\u00e9k\u00e9si , and G\u00e1bor Galambos . 2012. New lower bounds for certain classes of bin packing algorithms. Theor. Comput. Sci. 440--441 ( 2012 ), 1--13. DOI:https:\/\/doi.org\/10.1016\/j.tcs.2012.04.017 10.1016\/j.tcs.2012.04.017 J\u00e1nos Balogh, J\u00f3zsef B\u00e9k\u00e9si, and G\u00e1bor Galambos. 2012. New lower bounds for certain classes of bin packing algorithms. Theor. Comput. Sci. 440--441 (2012), 1--13. DOI:https:\/\/doi.org\/10.1016\/j.tcs.2012.04.017"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9185-z"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Heydrich Sandy","year":"2016","unstructured":"Sandy Heydrich and Rob van Stee . 2016 . Beating the harmonic lower bound for online bin packing . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916) . Article 41, 14 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2016.41 10.4230\/LIPIcs.ICALP.2016.41 Sandy Heydrich and Rob van Stee. 2016. Beating the harmonic lower bound for online bin packing. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916). Article 41, 14 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.41"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212014"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612675"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSVT.2015.2450152"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2393868"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935775"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585269"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.07.017"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.42"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90223-I"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35261-4_8"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364214","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3364214","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:26Z","timestamp":1750203866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364214"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,30]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3364214"],"URL":"https:\/\/doi.org\/10.1145\/3364214","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2019,9,30]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}