Online Bin Packing with Predictions
Open accessThe DOI matches its Crossref record; 56 of the 60 references it cites were found in a registry or an index.
Abstract
Bin packing is a classic optimization problem with a wide range of applications from load balancing to supply chain management. In this work, we study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a (potentially erroneous) prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with efficient tradeoffs between the consistency (i.e., the competitive ratio assuming no prediction error) and the robustness (i.e., the competitive ratio under adversarial error), and whose performance degrades near-optimally as a function of the prediction error. This is the first theoretical and experimental study of online bin packing in the realistic setting of learnable predictions. Previous work addressed only extreme cases with respect to the prediction error, and relied on overly powerful and error-free oracles.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974) · SIAM Journal on Computing · doi:10.1137/0203025 · Cited by 911
Approximation algorithms for bin packing: a survey
Coffman, E. G., Garey, M. R., & Johnson, D. S. (1996) · PWS Publishing Co. eBooks · Cited by 862
A Survey on Ensemble Learning for Data Stream Classification
Gomes, H. M., Barddal, J. P., Enembreck, F., & Bifet, A. (2018) · ACM Computing Surveys · doi:10.1145/3054925 · Cited by 579
Bin packing and cutting stock problems: Mathematical models and exact algorithms
Delorme, M., Iori, M., & Martello, S. (2016) · European Journal of Operational Research · doi:10.1016/j.ejor.2016.04.030 · Cited by 379
A simple on-line bin-packing algorithm
Lee, C. C., & Lee, D. T. (1985) · Journal of the ACM · doi:10.1145/3828.3833 · Cited by 357
Consolidating virtual machines with dynamic bandwidth demand in data centers
Wang, M., Meng, X., & Zhang, L. (2011) · 2011 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2011.5935254 · Cited by 339
Lower bounds and reduction procedures for the bin packing problem
Martello, S., & Toth, P. (1990) · Discrete Applied Mathematics · doi:10.1016/0166-218x(90)90094-s · Cited by 291
Mann, Z. Á. (2015) · ACM Computing Surveys · doi:10.1145/2797211 · Cited by 274
Approximation and online algorithms for multidimensional bin packing: A survey
Christensen, H. I., Khan, A., Pokutta, S., & Tetali, P. (2017) · Computer Science Review · doi:10.1016/j.cosrev.2016.12.001 · Cited by 237
Research works printed but not linked: 9
- Andrews, G. E. (1976). The Theory of Partitions . Addison-Wesley Publishing Company.
- Argue, C., Frieze, A. M., Gupta, A., & Seiler, C. (2022). Learning from a sample in online algorithms. In Proceedings of the 31st Conference on Neural Information Processing Systems (NeurIPS) .
- Balogh, J., B´ ek´ esi, J., D´ osa, G., Epstein, L., & Levin, A. (2021). A new lower bound for classic online bin packing. Algorithmica , 83 (7), 2047-2062.
- Csirik, J., Johnson, D. S., Kenyon, C., Orlin, J. B., Shor, P. W., & Weber, R. R. (2006a). On the sum-of-squares algorithm for bin packing. Journal of the ACM , 53 , 1-65.
- Csirik, J., Johnson, D. S., Kenyon, C., Orlin, J. B., Shor, P. W., & Weber, R. R. (2006b). On the sum-of-squares algorithm for bin packing. Journal of the ACM (JACM) , 53 (1), 1-65.
- de la Vega, W. F., & Lueker, G. S. (1981). Bin packing can be solved within 1+epsilon in linear time. Comb. , 1 (4), 349-355.
- Diakonikolas, I., Kontonis, V., Tzamos, C., Vakilian, A., & Zarifis, N. (2021). Learning online algorithms with distributional advice. In ICML , Vol. 139 of Proceedings of Machine Learning Research , pp. 2687-2696. PMLR.
- Gent, I. P. (1998). Heuristic solution of open bin packing problems. Journal of Heuristics , 3 (4), 299-304.
- Kamali, S., & L´ opez-Ortiz, A. (2015b). All-around near-optimal solutions for the online bin packing problem. In International Symposium on Algorithms and Computation (ISAAC) , pp. 727-739.
Cited by
Mathematical discoveries from program search with large language models
Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., et al. (2024) · Nature · doi:10.1038/s41586-023-06924-6 · Cited by 544
“In addition to the OR benchmarks, we also use FunSearch to evolve heuristics on bin packing instances sampled from a Weibull distribution, as these closely follow many real-world scheduling problems 24,47 (see Supplementary Information Appendix E.4 for details).”
MethodOnline computation with untrusted advice
Angelopoulos, S., Dürr, C., Jin, S., Kamali, S., & Renault, M. P. (2024) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2024.103545 · Cited by 76
Self-citationNon-Clairvoyant Scheduling with Predictions
Im, S., Kumar, R., Qaem, M. M., & Purohit, M. (2021) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3409964.3461790 · Cited by 68
Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets
Lee, R., Sun, B., Hajiesmaili, M., & Lui, J. C. S. (2024) · ACM International Conference on Future Energy Systems (e-Energy) · doi:10.1145/3632775.3639590 · Cited by 25
Online Interval Scheduling with Predictions
Boyar, J., Favrholdt, L. M., Kamali, S., & Larsen, K. S. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38906-1_14 · Cited by 21
Self-citation
Metadata
- Authors
- Angelopoulos, S., Kamali, S., & Shadkami, K.
- Affiliations
- Centre National de la Recherche Scientifique (FR)
- York University (CA)
- University of Manitoba (CA)
- Venue
- Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
- Published
- 2022-07
- Volume
- 78
- Issue
- 9
- Pages
- 4574-4580
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W4225709049
- Cited by
- 28
- References
- 60
- Citations by year
- 2026: 7 · 2025: 8 · 2024: 8 · 2023: 3 · 2022: 1
- FWCI
- 2.22
- Type
- journal article
- Language
- en
- Open access
- diamond
- doi.org
- Licence
- cc-by
- Locations
- Journal of Artificial Intelligence Research (publishedVersion, cc-by)
- International Joint Conference on Artificial Intelligence (publishedVersion)
- HAL (submittedVersion, other-oa)
- HAL (submittedVersion)
- arXiv (Cornell University)
- Funders
- Agence Nationale de la Recherche (ANR‐19, ANR-23-CE48-0010, ANR-19-CE48-0016)
- Centre National de la Recherche Scientifique
- Fondation Mathématique Jacques Hadamard
- Natural Sciences and Engineering Research Council of Canada (crc-2018-00059)
- Topics
- Physical Sciences › Mathematics › Theoretical Computer Science › Optimization and Search Problems
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Optimization and Packing Problems
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Keywords
- online bin packing, prediction error, competitive ratio, robustness, adversarial errors
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Online Bin Packing with Predictions. https://app.cochat.ai/papers/10.24963/ijcai.2022/635
- The paper
- Angelopoulos, S., Kamali, S., & Shadkami, K. (2022). Online Bin Packing with Predictions. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. https://doi.org/10.24963/ijcai.2022/635
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.