{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:43:47Z","timestamp":1755999827963,"version":"3.41.0"},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,9,4]],"date-time":"2014-09-04T00:00:00Z","timestamp":1409788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2014,9,4]]},"abstract":"<jats:p>In the static bin packing problem, items of diffierent sizes must be packed into bins or servers with unit capacity in a way that minimizes the number of bins used, and it is well-known to be a hard combinatorial problem. Best-Fit is among the simplest online heuristics for this problem. Motivated by the problem of packing virtual machines in servers in the cloud, we consider the dynamic version of this problem, when jobs arrive randomly over time and leave the system after completion of their service. We analyze the uid limits of the system under an asymptotic Best-Fit algorithm and show that it asymptotically minimizes the number of servers used in steady state (on the uid scale). The significance of the result is due to the fact that Best-Fit seems to achieve the best performance in practice.<\/jats:p>","DOI":"10.1145\/2667522.2667543","type":"journal-article","created":{"date-parts":[[2014,9,5]],"date-time":"2014-09-05T19:12:56Z","timestamp":1409944376000},"page":"64-66","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Asymptotic optimality of BestFit for stochastic bin packing"],"prefix":"10.1145","volume":"42","author":[{"given":"Javad","family":"Ghaderi","sequence":"first","affiliation":[{"name":"Columbia University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuan","family":"Zhong","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Srikant","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"e_1_2_1_2_1","volume-title":"Proc. Foundations of Computer Science","author":"Kenyon C.","year":"2000","unstructured":"C. Kenyon , M. Mitzenmacher, Linear waste of Best Fit bin packing on skewed distributions . Proc. Foundations of Computer Science , 2000 . C. Kenyon, M. Mitzenmacher, Linear waste of Best Fit bin packing on skewed distributions. Proc. Foundations of Computer Science, 2000."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1184"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465547"},{"key":"e_1_2_1_5_1","volume-title":"Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints. submitted to Queueing Systems","author":"Stolyar A.L.","year":"2013","unstructured":"A.L. Stolyar , Y. Zhong . Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints. submitted to Queueing Systems , 2013 . A.L. Stolyar, Y. Zhong. Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints. submitted to Queueing Systems, 2013."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195815"},{"key":"e_1_2_1_7_1","unstructured":"V. Gupta A. Radovanovic. Online stochastic bin packing arXiv:1211.2687.  V. Gupta A. Radovanovic. Online stochastic bin packing arXiv:1211.2687."}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2667522.2667543","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2667522.2667543","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:16Z","timestamp":1750229776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2667522.2667543"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,4]]},"references-count":7,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,9,4]]}},"alternative-id":["10.1145\/2667522.2667543"],"URL":"https:\/\/doi.org\/10.1145\/2667522.2667543","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2014,9,4]]},"assertion":[{"value":"2014-09-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}