{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T02:18:16Z","timestamp":1781835496926,"version":"3.54.5"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T00:00:00Z","timestamp":1745971200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Google India Research Award, SERB Core Research Grant","award":["CRG\/2022\/001176"],"award-info":[{"award-number":["CRG\/2022\/001176"]}]},{"name":"Walmart Center for Tech Excellence at IISc","award":["WMGT-23-0001"],"award-info":[{"award-number":["WMGT-23-0001"]}]},{"name":"Google PhD Fellowship Program"},{"DOI":"10.13039\/100007780","name":"Indian Institute of Science Bengaluru","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"\n We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given\n n<\/jats:italic>\n items with sizes in\n \n \\((0,1]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and the goal is to pack them into the minimum number of unit-sized bins.\n <\/jats:p>\n \n First, we study bin packing under the i.i.d. model, where item sizes are sampled independently and identically from a distribution in\n \n \\((0,1]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Both the distribution and the total number of items are unknown. The items arrive one by one and their sizes are revealed upon their arrival and they must be packed immediately and irrevocably in bins of size 1. We provide a simple meta-algorithm that takes an offline\n \n \\(\\alpha\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -asymptotic approximation algorithm and provides a polynomial-time\n \n \\((\\alpha+\\varepsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -competitive algorithm for online bin packing under the i.i.d. model, where\n \n \\(\\varepsilon > 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time\n \n \\((1+\\varepsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -competitive algorithm for online bin packing under i.i.d. model, thus settling the problem.\n <\/jats:p>\n \n We then study the random-order model, where an adversary chooses the instance, but the order of arrival of items in the instance is drawn uniformly at random from the set of all permutations of the items. Kenyon\u2019s seminal result (1996) showed that the Best-Fit algorithm has a competitive ratio of at most\n \n \\(3\/2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in the random-order model, and conjectured the ratio to be\n \n \\(\\approx 1.15\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . However, it has been a long-standing open problem to break the barrier of\n \n \\(3\/2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n even for special cases. Recently, Albers et al. (2021) showed an improvement by proving that in the special case when all the item sizes are greater than\n \n \\(1\/3\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , Best-Fit has a competitive ratio of at most\n \n \\(5\/4\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in the random-order model. In this work, we settle this special case by showing that Best-Fit has a competitive ratio of exactly 1, i.e., Best-Fit performs almost optimally in this special case in the random-order model. We also make further progress by breaking the barrier of\n \n \\(3\/2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for the\n 3-Partition<\/jats:italic>\n problem, a notoriously hard special case of bin packing, where all item sizes lie in\n \n \\((1\/4,1\/2]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1145\/3728642","type":"journal-article","created":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T15:53:56Z","timestamp":1744386836000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Near-optimal Algorithms for Stochastic Online Bin Packing"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-9093-3677","authenticated-orcid":false,"given":"Nikhil","family":"Ayyadevara","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Michigan, Ann Arbor, Michigan, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8742-8939","authenticated-orcid":false,"given":"Rajni","family":"Dabas","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Northwestern University, Evanston, Illinois, USA and Department of Computer Science, University of Delhi, New Delhi, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7505-1687","authenticated-orcid":false,"given":"Arindam","family":"Khan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1090-2721","authenticated-orcid":false,"given":"K. V. N.","family":"Sreenivas","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,5,14]]},"reference":[{"issue":"9","key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"2833","DOI":"10.1007\/s00453-021-00844-5","article-title":"Best fit bin packing with random order revisited","volume":"83","author":"Albers Susanne","year":"2021","unstructured":"Susanne Albers, Arindam Khan, and Leon Ladewig. 2021. Best fit bin packing with random order revisited. Algorithmica 83, 9 (2021), 2833\u20132858.","journal-title":"Algorithmica"},{"issue":"6","key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"1750","DOI":"10.1007\/s00453-021-00801-2","article-title":"Improved online algorithms for knapsack and GAP in the random order model","volume":"83","author":"Albers Susanne","year":"2021","unstructured":"Susanne Albers, Arindam Khan, and Leon Ladewig. 2021. Improved online algorithms for knapsack and GAP in the random order model. Algorithmica 83, 6 (2021), 1750\u20131785.","journal-title":"Algorithmica"},{"issue":"2","key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1137\/0602019","article-title":"A tight asymptotic bound for next-fit-decreasing bin-packing","volume":"2","author":"Baker Brenda S.","year":"1981","unstructured":"Brenda S. Baker and Edward G. Coffman, Jr. 1981. A tight asymptotic bound for next-fit-decreasing bin-packing. SIAM Journal on Algebraic Discrete Methods 2, 2 (1981), 147\u2013152.","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"e_1_3_2_5_2","first-page":"5:1","article-title":"A new and improved algorithm for online bin packing","volume":"112","author":"Balogh J\u00e1nos","year":"2018","unstructured":"J\u00e1nos Balogh, J\u00f3zsef B\u00e9k\u00e9si, Gy\u00f6rgy D\u00f3sa, Leah Epstein, and Asaf Levin. 2018. A new and improved algorithm for online bin packing. In ESA, Vol. 112, 5:1\u20135:14.","journal-title":"ESA"},{"issue":"7","key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"2047","DOI":"10.1007\/s00453-021-00818-7","article-title":"A new lower bound for classic online bin packing","volume":"83","author":"Balogh J\u00e1nos","year":"2021","unstructured":"J\u00e1nos Balogh, J\u00f3zsef B\u00e9k\u00e9si, Gy\u00f6rgy D\u00f3sa, Leah Epstein, and Asaf Levin. 2021. A new lower bound for classic online bin packing. Algorithmica 83, 7 (2021), 2047\u20132062.","journal-title":"Algorithmica"},{"issue":"3","key":"e_1_3_2_7_2","first-page":"1361","article-title":"Concentration inequalities for sampling without replacement","volume":"21","author":"Bardenet R\u00e9mi","year":"2015","unstructured":"R\u00e9mi Bardenet and Odalric-Ambrym Maillard. 2015. Concentration inequalities for sampling without replacement. Bernoulli 21, 3 (2015), 1361\u20131385.","journal-title":"Bernoulli"},{"issue":"1","key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1006\/jcss.1999.1667","article-title":"A 5\/4 linear time bin packing algorithm","volume":"60","author":"B\u00e9k\u00e9si J\u00f3zsef","year":"2000","unstructured":"J\u00f3zsef B\u00e9k\u00e9si, G\u00e1bor Galambos, and Hans Kellerer. 2000. A 5\/4 linear time bin packing algorithm. Journal of Computer and System Sciences 60, 1 (2000), 145\u2013160.","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_3_2_9_2","first-page":"279","article-title":"Some unexpected expected behavior results for bin packing","author":"Bentley Jon Louis","year":"1984","unstructured":"Jon Louis Bentley, David S. Johnson, Frank Thomson Leighton, Catherine C. McGeoch, and Lyle A. McGeoch. 1984. Some unexpected expected behavior results for bin packing. In STOC, 279\u2013288.","journal-title":"STOC"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"e_1_3_2_11_2","unstructured":"Carsten Oliver Fischer. 2019. New Results on the Probabilistic Analysis of Online Bin Packing and Its Variants. Ph.D. thesis. Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn."},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/978-1-4419-7997-1_35","volume-title":"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. In Handbook of Combinatorial Optimization. Panos M. Pardalos, Ding-Zhu Du, and Ronald L. Graham (Eds.), Springer, New York, 455\u2013531."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177011082"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/251040.251048"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(80)90050-9"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120583"},{"issue":"4","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","article-title":"Bin packing can be solved within 1+epsilon in linear time","volume":"1","author":"Fernandez de la Vega W.","year":"1981","unstructured":"W. Fernandez de la Vega and George S. Lueker. 1981. Bin packing can be solved within 1+epsilon in linear time. Combinatorica 1, 4 (1981), 349\u2013355.","journal-title":"Combinatorica"},{"issue":"4","key":"e_1_3_2_18_2","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1287\/moor.1080.0330","article-title":"Approximating the stochastic knapsack problem: The benefit of adaptivity","volume":"33","author":"Dean Brian C.","year":"2008","unstructured":"Brian C. Dean, Michel X. Goemans, and Jan Vondr\u00e1k. 2008. Approximating the stochastic knapsack problem: The benefit of adaptivity. Mathematics of Operations Research 33, 4 (2008), 945\u2013964.","journal-title":"Mathematics of Operations Research"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483704"},{"key":"e_1_3_2_20_2","first-page":"117","article-title":"Online stochastic matching: Beating 1-1\/e","author":"Feldman Jon","year":"2009","unstructured":"Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan. 2009. Online stochastic matching: Beating 1-1\/e. In FOCS, 117\u2013126.","journal-title":"FOCS"},{"issue":"3","key":"e_1_3_2_21_2","first-page":"282","article-title":"Who solved the secretary problem?","volume":"4","author":"Ferguson Thomas S.","year":"1989","unstructured":"Thomas S. Ferguson. 1989. Who solved the secretary problem? Statistical Science 4, 3 (1989), 282\u2013289.","journal-title":"Statistical Science"},{"key":"e_1_3_2_22_2","first-page":"469","article-title":"Probabilistic analysis of the dual next-fit algorithm for bin covering","author":"Fischer Carsten","year":"2016","unstructured":"Carsten Fischer and Heiko R\u00f6glin. 2016. Probabilistic analysis of the dual next-fit algorithm for bin covering. In LATIN, 469\u2013482.","journal-title":"LATIN"},{"key":"e_1_3_2_23_2","first-page":"461","article-title":"Probabilistic analysis of online (class-constrained) bin packing and bin covering","volume":"10807","author":"Fischer Carsten","year":"2018","unstructured":"Carsten Fischer and Heiko R\u00f6glin. 2018. Probabilistic analysis of online (class-constrained) bin packing and bin covering. In LATIN, Vol. 10807. Springer, 461\u2013474.","journal-title":"LATIN"},{"issue":"6","key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"1649","DOI":"10.1137\/09076725X","article-title":"Online and stochastic survivable network design","volume":"41","author":"Gupta Anupam","year":"2012","unstructured":"Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi. 2012. Online and stochastic survivable network design. SIAM Journal on Computing 41, 6 (2012), 1649\u20131672.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1287\/moor.2019.1049","article-title":"Stochastic load balancing on unrelated machines","volume":"46","author":"Gupta Anupam","year":"2021","unstructured":"Anupam Gupta, Amit Kumar, Viswanath Nagarajan, and Xiangkun Shen. 2021. Stochastic load balancing on unrelated machines. Mathematics of Operations Research 46, 1 (2021), 115\u2013133.","journal-title":"Mathematics of Operations Research"},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1017\/9781108637435.015","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"Gupta Anupam","year":"2020","unstructured":"Anupam Gupta and Sahil Singla. 2020. Random-order models. In Beyond the Worst-Case Analysis of Algorithms. Tim Roughgarden (Ed.), Cambridge University Press, 234\u2013258."},{"key":"e_1_3_2_27_2","first-page":"4177","article-title":"Bin packing under random-order: Breaking the barrier of 3\/2","author":"Hebbar Anish","year":"2024","unstructured":"Anish Hebbar, Arindam Khan, and K. V. N. Sreenivas. 2024. Bin packing under random-order: Breaking the barrier of 3\/2. In SODA, 4177\u20134219.","journal-title":"SODA"},{"key":"e_1_3_2_28_2","first-page":"2616","article-title":"A logarithmic additive integrality gap for bin packing","author":"Hoberg Rebecca","year":"2017","unstructured":"Rebecca Hoberg and Thomas Rothvoss. 2017. A logarithmic additive integrality gap for bin packing. In SODA, 2616\u20132625.","journal-title":"SODA"},{"key":"e_1_3_2_29_2","unstructured":"David S. Johnson. 1973. Near-Optimal Bin Packing Algorithms. Ph.D. thesis. Massachusetts Institute of Technology."},{"issue":"3","key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","article-title":"Fast algorithms for bin packing","volume":"8","author":"Johnson David S.","year":"1974","unstructured":"David S. Johnson. 1974. Fast algorithms for bin packing. Journal of Computer and System Sciences 8, 3 (1974), 272\u2013314.","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(85)90022-6"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/1410890.1410986"},{"key":"e_1_3_2_34_2","first-page":"312","article-title":"An efficient approximation scheme for the one-dimensional bin-packing problem","author":"Karmarkar Narendra","year":"1982","unstructured":"Narendra Karmarkar and Richard M. Karp. 1982. An efficient approximation scheme for the one-dimensional bin-packing problem. In FOCS, 312\u2013320.","journal-title":"FOCS"},{"key":"e_1_3_2_35_2","first-page":"289","article-title":"A probabilistic analysis of multidimensional bin packing problems","author":"Karp Richard M.","year":"1984","unstructured":"Richard M. Karp, Michael Luby, and A. Marchetti-Spaccamela. 1984. A probabilistic analysis of multidimensional bin packing problems. In STOC, 289\u2013298.","journal-title":"STOC"},{"key":"e_1_3_2_36_2","first-page":"359","article-title":"Best-fit bin-packing with random order","author":"Kenyon Claire","year":"1996","unstructured":"Claire Kenyon. 1996. Best-fit bin-packing with random order. In SODA, 359\u2013364.","journal-title":"SODA"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3833"},{"key":"e_1_3_2_38_2","volume-title":"Robust On-Line Bin Packing Algorithms","author":"Lee Chan C.","year":"1987","unstructured":"Chan C. Lee and Der-Tsai Lee. 1987. Robust On-Line Bin Packing Algorithms. Technical Report. Northwestern University."},{"issue":"2","key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02124678","article-title":"Tight bounds for minimax grid matching with applications to the average case analysis of algorithms","volume":"9","author":"Leighton Tom","year":"1989","unstructured":"Tom Leighton and Peter Shor. 1989. Tight bounds for minimax grid matching with applications to the average case analysis of algorithms. Combinatorica 9, 2 (1989), 161\u2013187.","journal-title":"Combinatorica"},{"key":"e_1_3_2_40_2","first-page":"597","article-title":"Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs","author":"Mahdian Mohammad","year":"2011","unstructured":"Mohammad Mahdian and Qiqi Yan. 2011. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. In STOC, 597\u2013606.","journal-title":"STOC"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(88)90069-8"},{"key":"e_1_3_2_42_2","first-page":"253","article-title":"Beck\u2019s three permutations conjecture: A counterexample and some consequences","author":"Newman Alantha","year":"2012","unstructured":"Alantha Newman, Ofer Neiman, and Aleksandar Nikolov. 2012. Beck\u2019s three permutations conjecture: A counterexample and some consequences. In FOCS, 253\u2013262.","journal-title":"FOCS"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90077-X"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1080\/02331939408843965"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.1.177"},{"issue":"1","key":"e_1_3_2_46_2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1090\/S0002-9947-1988-0936807-0","article-title":"Exact bounds for the stochastic upward matching problem","volume":"307","author":"Rhee Wansoo T.","year":"1988","unstructured":"Wansoo T. Rhee and Michel Talagrand. 1988. Exact bounds for the stochastic upward matching problem. Transactions of the American Mathematical Society 307, 1 (1988), 109\u2013125.","journal-title":"Transactions of the American Mathematical Society"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222074"},{"issue":"2","key":"e_1_3_2_48_2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF02579171","article-title":"The average-case analysis of some on-line algorithms for bin packing","volume":"6","author":"Shor Peter W.","year":"1986","unstructured":"Peter W. Shor. 1986. The average-case analysis of some on-line algorithms for bin packing. Combinatorica 6, 2 (1986), 179\u2013200.","journal-title":"Combinatorica"},{"key":"e_1_3_2_49_2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970074","volume-title":"Ten Lectures on the Probabilistic Method","author":"Spencer Joel","year":"1994","unstructured":"Joel Spencer. 1994. Ten Lectures on the Probabilistic Method. SIAM."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3728642","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3728642","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:36Z","timestamp":1750295916000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3728642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,30]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3728642"],"URL":"https:\/\/doi.org\/10.1145\/3728642","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,30]]},"assertion":[{"value":"2024-01-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}