2026-07-22T10:47:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24257 2025-11-12T13:39:31Z ddc:004 open_access

Lower Bounds for Several Standard Bin Packing Algorithms in the Random Order Model Epstein, Leah Levin, Asaf Bin packing Best Fit Random order Bounded space algorithms We consider the performance of standard bin packing algorithms in the random order model. We provide an improved lower bound of 1.15582656 on the asymptotic approximation ratio of Best Fit (BF) for randomly ordered inputs. We also show lower bounds on the asymptotic approximation ratio for two bounded space bin packing algorithms in this model, namely for 2-BF and 2-FF. These are well-studied bounded space algorithms and the first one has the same asymptotic worst-case performance as BF. However, the resulting lower bounds on their performances in the random order model are much higher than that of BF. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leah Epstein and Asaf Levin 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.26 urn:nbn:de:0030-drops-242577 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.26 eng https://creativecommons.org/licenses/by/4.0/legalcode