Papers › Bin Packing under Random-Order: Breaking the Barrier of 3/2
Bin Packing under Random-Order: Breaking the Barrier of 3/2
Anish Hebbar, Arindam Khan, K. V. N. Sreenivas
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Best-Fit is one of the most prominent and practically used algorithms for the bin packing problem, where a set of items with associated sizes needs to be packed in the minimum number of unit-capacity bins. Kenyon [SODA '96] studied online bin packing under random-order arrival, where the adversary chooses the list of items, but the items arrive one by one according to an arrival order drawn uniformly randomly from the set of all permutations of the items. Kenyon's seminal result established an upper bound of $1.5$ and a lower bound of $1.08$ on the random-order ratio of Best-Fit, and it was conjectured that the true ratio is ≈1.15. The conjecture, if true, will also imply that Best-Fit (on randomly permuted input) has the best performance guarantee among all the widely-used simple algorithms for (offline) bin packing. This conjecture has remained one of the major open problems in the area, as highlighted in the recent survey on random-order models by Gupta and Singla [Beyond the Worst-Case Analysis of Algorithms '20]. Recently, Albers et al. [Algorithmica '21] improved the upper bound to $1.25$ for the special case when all the item sizes are greater than 1/3, and they improve the lower bound to $1.1$. Ayyadevara et al. [ICALP '22] obtained an improved result for the special case when all the item sizes lie in (1/4, 1/2], which corresponds to the $3$-partition problem. The upper bound of 3/2 for the general case, however, has remained unimproved. In this paper, we make the first progress towards the conjecture, by showing that Best-Fit achieves a random-order ratio of at most 1.5 - ε, for a small constant ε>0. Furthermore, we establish an improved lower bound of $1.144$ on the random-order ratio of Best-Fit, nearly reaching the conjectured ratio.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections