{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T15:49:12Z","timestamp":1774540152288,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"European Research Council","award":["691672"],"award-info":[{"award-number":["691672"]}]},{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a seminal work, Kenyon [SODA 1996] introduced the (asymptotic) <jats:italic>random order ratio<\/jats:italic> as an alternative performance measure for online algorithms. Here, an adversary specifies the items, but the order of arrival is drawn uniformly at random. Kenyon\u2019s result establishes lower and upper bounds of 1.08 and 1.5, respectively, for the random order ratio of Best Fit. Although this type of analysis model became increasingly popular in the field of online algorithms, no progress has been made for the Best Fit algorithm after the result of Kenyon. We study the random order ratio of Best Fit and tighten the long-standing gap by establishing an improved lower bound of 1.10. For the case where all items are larger than 1\/3, we show that the random order ratio converges quickly to 1.25. It is the existence of such large items that crucially determines the performance of Best Fit in the general case. Moreover, this case is closely related to the classical maximum-cardinality matching problem in the fully online model. As a side product, we show that Best Fit satisfies a monotonicity property on such instances, unlike in the general case. In addition, we initiate the study of the <jats:italic>absolute<\/jats:italic> random order ratio for this problem. In contrast to asymptotic ratios, absolute ratios must hold even for instances that can be packed into a small number of bins. We show that the absolute random order ratio of Best Fit is at least 1.3. For the case where all items are larger than 1\/3, we derive upper and lower bounds of 21\/16 and 1.2, respectively.<\/jats:p>","DOI":"10.1007\/s00453-021-00844-5","type":"journal-article","created":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T18:04:43Z","timestamp":1625162683000},"page":"2833-2858","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Best Fit Bin Packing with Random Order Revisited"],"prefix":"10.1007","volume":"83","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[]},{"given":"Arindam","family":"Khan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5998-8154","authenticated-orcid":false,"given":"Leon","family":"Ladewig","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,1]]},"reference":[{"key":"844_CR1","doi-asserted-by":"crossref","unstructured":"Al-Herz, A., Pothen, A.: A 2\/3-approximation algorithm for vertex-weighted matching. In: Discrete Applied Mathematics (2019). ((in press))","DOI":"10.1016\/j.dam.2019.09.013"},{"key":"844_CR2","unstructured":"Albers, S., Khan, A., Ladewig, L.: Best fit bin packing with random order revisited. In: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 7:1\u20137:15 (2020)"},{"key":"844_CR3","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., Levin, A.: A new and improved algorithm for online bin packing. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA), LIPIcs, vol. 112, pp. 5:1\u20135:14 (2018)"},{"key":"844_CR4","doi-asserted-by":"crossref","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., Levin, A.: A new lower bound for classic online bin packing. In: Approximation and Online Algorithms\u201417th International Workshop, (WAOA), Lecture Notes in Computer Science, vol. 11926, pp. 18\u201328. Springer (2019)","DOI":"10.1007\/978-3-030-39479-0_2"},{"issue":"13\u201314","key":"844_CR5","doi-asserted-by":"publisher","first-page":"1914","DOI":"10.1016\/j.dam.2012.04.012","volume":"160","author":"J Boyar","year":"2012","unstructured":"Boyar, J., D\u00f3sa, G., Epstein, L.: On the absolute approximation ratio for first fit and related results. Discret. Appl. Math. 160(13\u201314), 1914\u20131923 (2012)","journal-title":"Discret. Appl. Math."},{"key":"844_CR6","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.tcs.2014.06.029","volume":"556","author":"MG Christ","year":"2014","unstructured":"Christ, M.G., Favrholdt, L.M., Larsen, K.S.: Online bin covering: expectations vs. guarantees. Theor. Comput. Sci 556, 71\u201384 (2014)","journal-title":"Theor. Comput. Sci"},{"key":"844_CR7","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63\u201379 (2017)","journal-title":"Comput. Sci. Rev."},{"key":"844_CR8","doi-asserted-by":"crossref","unstructured":"Coffman Jr., E.G., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: survey and classification. In: Handbook of Combinatorial Optimization, pp. 455\u2013531. Springer, New York (2013)","DOI":"10.1007\/978-1-4419-7997-1_35"},{"issue":"14","key":"844_CR9","doi-asserted-by":"publisher","first-page":"2810","DOI":"10.1016\/j.dam.2007.11.004","volume":"156","author":"EG Coffman Jr","year":"2008","unstructured":"Coffman, E.G., Jr., Csirik, J., R\u00f3nyai, L., Zsb\u00e1n, A.: Random-order bin packing. Discret. Appl. Math. 156(14), 2810\u20132816 (2008)","journal-title":"Discret. Appl. Math."},{"key":"844_CR10","volume-title":"Probabilistic Analysis of Packing and Partitioning Algorithms. Wiley-Interscience Series in Discrete Mathematics and Optimization","author":"EG Coffman Jr","year":"1991","unstructured":"Coffman, E.G., Jr., Lueker, G.S.: Probabilistic Analysis of Packing and Partitioning Algorithms. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Hoboken (1991)"},{"key":"844_CR11","unstructured":"D\u00f3sa, G., Sgall, J.: First fit bin packing: a tight analysis. In: 30th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol.\u00a020, pp. 538\u2013549 (2013)"},{"key":"844_CR12","doi-asserted-by":"crossref","unstructured":"D\u00f3sa, G., Sgall, J.: Optimal analysis of best fit bin packing. In: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pp. 429\u2013441 (2014)","DOI":"10.1007\/978-3-662-43948-7_36"},{"key":"844_CR13","doi-asserted-by":"crossref","unstructured":"Fischer, C., R\u00f6glin, H.: Probabilistic analysis of the dual next-fit algorithm for bin covering. In: LATIN 2016: Theoretical Informatics\u201412th Latin American Symposium, pp. 469\u2013482 (2016)","DOI":"10.1007\/978-3-662-49529-2_35"},{"key":"844_CR14","doi-asserted-by":"crossref","unstructured":"Fischer, C., R\u00f6glin, H.: Probabilistic analysis of online (class-constrained) bin packing and bin covering. In: LATIN 2018: Theoretical Informatics\u201413th Latin American Symposium, Lecture Notes in Computer Science, vol. 10807, pp. 461\u2013474. Springer (2018)","DOI":"10.1007\/978-3-319-77404-6_34"},{"key":"844_CR15","doi-asserted-by":"crossref","unstructured":"Gamlath, B., Kapralov, M., Maggiori, A., Svensson, O., Wajc, D.: Online matching with general arrivals. In: 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 26\u201337 (2019)","DOI":"10.1109\/FOCS.2019.00011"},{"key":"844_CR16","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R.L., Ullman, J.D.: Worst-case analysis of memory allocation algorithms. In: Proceedings of the 4th Annual ACM Symposium on Theory of Computing (STOC), pp. 143\u2013150 (1972)","DOI":"10.1145\/800152.804907"},{"issue":"3","key":"844_CR17","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: Strong NP-completeness results: motivation, examples, and implications. J. ACM 25(3), 499\u2013508 (1978)","journal-title":"J. ACM"},{"issue":"2","key":"844_CR18","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"844_CR19","doi-asserted-by":"crossref","unstructured":"Gupta, A., Singla, S.: Random-order models. CoRR, arXiv:abs\/2002.12159 (2020)","DOI":"10.1017\/9781108637435.015"},{"key":"844_CR20","doi-asserted-by":"crossref","unstructured":"Hoberg, R., Rothvoss, T.: A logarithmic additive integrality gap for bin packing. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2616\u20132625 (2017)","DOI":"10.1137\/1.9781611974782.172"},{"key":"844_CR21","doi-asserted-by":"crossref","unstructured":"Huang, Z., Kang, N., Tang, Z.G., Wu, X., Zhang, Y., Zhu, X.: How to match when all vertices arrive online. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 17\u201329 (2018)","DOI":"10.1145\/3188745.3188858"},{"key":"844_CR22","doi-asserted-by":"crossref","unstructured":"Huang, Z., Peng, B., Tang, Z.G., Tao, R., Wu, X., Zhang, Y.: Tight competitive ratios of classic matching algorithms in the fully online model. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2875\u20132886 (2019)","DOI":"10.1137\/1.9781611975482.178"},{"issue":"3","key":"844_CR23","doi-asserted-by":"publisher","first-page":"38:1","DOI":"10.1145\/3326169","volume":"15","author":"Z Huang","year":"2019","unstructured":"Huang, Z., Tang, Z.G., Wu, X., Zhang, Y.: Online vertex-weighted bipartite matching: beating 1-1\/e with random arrivals. ACM Trans. Algorithms 15(3), 38:1-38:15 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"844_CR24","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8(3), 272\u2013314 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"844_CR25","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A.J., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299\u2013325 (1974)","journal-title":"SIAM J. Comput."},{"key":"844_CR26","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"844_CR27","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Ortiz, H. (ed.) Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"key":"844_CR28","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 359\u2013364 (1996)"},{"issue":"3","key":"844_CR29","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple on-line bin-packing algorithm. J. ACM 32(3), 562\u2013572 (1985)","journal-title":"J. ACM"},{"key":"844_CR30","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107","volume-title":"Markov Chains and Mixing Times","author":"DA Levin","year":"2017","unstructured":"Levin, D.A., Peres, Y.: Markov Chains and Mixing Times, vol. 107. American Mathematical Society, Providence (2017)"},{"key":"844_CR31","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"issue":"4","key":"844_CR32","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2013","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265\u2013368 (2013)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"3","key":"844_CR33","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0166-218X(88)90069-8","volume":"21","author":"FD Murgolo","year":"1988","unstructured":"Murgolo, F.D.: Anomalous behavior in bin packing algorithms. Discret. Appl. Math. 21(3), 229\u2013243 (1988)","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"844_CR34","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0020-0190(89)90077-X","volume":"31","author":"PV Ramanan","year":"1989","unstructured":"Ramanan, P.V.: Average-case analysis of the smart next fit algorithm. Inf. Process. Lett. 31(5), 221\u2013225 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"844_CR35","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","volume":"10","author":"PV Ramanan","year":"1989","unstructured":"Ramanan, P.V., Brown, D.J., Lee, C.C., Lee, D.T.: On-line bin packing in linear time. J. Algorithms 10(3), 305\u2013326 (1989)","journal-title":"J. Algorithms"},{"issue":"5","key":"844_CR36","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"SS Seiden","year":"2002","unstructured":"Seiden, S.S.: On the online bin packing problem. J. ACM 49(5), 640\u2013671 (2002)","journal-title":"J. ACM"},{"issue":"2","key":"844_CR37","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BF02579171","volume":"6","author":"PW Shor","year":"1986","unstructured":"Shor, P.W.: The average-case analysis of some on-line algorithms for bin packing. Combinatorica 6(2), 179\u2013200 (1986)","journal-title":"Combinatorica"},{"key":"844_CR38","volume-title":"The Performance of a Memory Allocation Algorithm","author":"J Ullman","year":"1971","unstructured":"Ullman, J.: The Performance of a Memory Allocation Algorithm, vol. 47. Department of Electrical Engineering, Computer Science Laboratory, Princeton University, Princeton (1971)"},{"issue":"4","key":"844_CR39","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"WF de la Vega","year":"1981","unstructured":"de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within 1+epsilon in linear time. Combinatorica 1(4), 349\u2013355 (1981)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00844-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00844-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00844-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T11:08:19Z","timestamp":1628161699000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00844-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,1]]},"references-count":39,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["844"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00844-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,1]]},"assertion":[{"value":"13 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}