Optimal asymptotic competitiveness for online bin packing
An input is a finite sequence $I = (s_1, \dots, s_n)$ of rational item sizes $0 < s_i \le 1$, whose length is not announced. A deterministic online algorithm $A$ receives the items one at a time and must place each one, irrevocably, into a bin of capacity $1$ before seeing the next, so that the sizes in every bin sum to at most $1$; arbitrarily many bins are available, and no restriction is placed on its computation time. It has no advice, predictions or other information about future items. Let $A(I)$ be the number of nonempty bins it uses, let $\operatorname{OPT}(I)$ be the minimum number of bins for $I$ when the whole sequence is known in advance, and let $$R_\infty(A) = \lim_{N \to \infty} \sup_{I :\ \operatorname{OPT}(I) \ge N} \frac{A(I)}{\operatorname{OPT}(I)}, \qquad R_* = \inf_A R_\infty(A),$$ the infimum over all such algorithms.
Yao proved that $R_\infty(A) \ge 3/2$ for every online algorithm $A$ and gave one with $R_\infty(A) = 5/3$. Balogh, Békési, Dósa, Epstein and Levin proved $$R_* \ge \frac{1363 - \sqrt{1387369}}{120} \approx 1.54278$$ (2021), and the same authors gave an online algorithm $A$ with $R_\infty(A) \le 1.57829$ (2018).
Problem. Determine the exact value of $R_*$.
Source: A classical question going back to Yao (1980), who proved the first lower bound, 3/2; stated in this form by AIM — Open Applied Problems, after Balogh, Békési, Dósa, Epstein and Levin (2018, 2021).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, bin packing, competitive ratios, online algorithms
References
@article{yao1980,
author = {Yao, Andrew Chi-Chih},
title = {New algorithms for bin packing},
journal = {J. ACM},
volume = {27},
number = {2},
year = {1980},
pages = {207--227},
doi = {10.1145/322186.322187},
}
@article{balogh2021,
author = {Balogh, J{\'a}nos and B{\'e}k{\'e}si, J{\'o}zsef and D{\'o}sa, Gy{\"o}rgy and Epstein, Leah and Levin, Asaf},
title = {A new lower bound for classic online bin packing},
journal = {Algorithmica},
volume = {83},
number = {7},
year = {2021},
pages = {2047--2062},
doi = {10.1007/s00453-021-00818-7},
eprint = {1807.05554},
archivePrefix = {arXiv},
}
@inproceedings{balogh2018,
author = {Balogh, J{\'a}nos and B{\'e}k{\'e}si, J{\'o}zsef and D{\'o}sa, Gy{\"o}rgy and Epstein, Leah and Levin, Asaf},
title = {A new and improved algorithm for online bin packing},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {112},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
year = {2018},
pages = {5:1--5:14},
doi = {10.4230/LIPIcs.ESA.2018.5},
eprint = {1707.01728},
archivePrefix = {arXiv},
}
@misc{aim-online-bin-packing-optimal-ratio,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Optimal asymptotic competitiveness for online bin packing}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/315-online-bin-packing-optimal-ratio.md},
note = {Entry 315 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00455, "Optimal asymptotic competitiveness for online bin packing", clopen.solutions.