CoChat

Online Bin Packing with Predictions

Open access
Angelopoulos, Spyros, Kamali, Shahin, Shadkami, Kimia · 2022 · Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence

The 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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.24963/ijcai.2022/635

Cites

56 of 56 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 56 references

Research works printed but not linked: 9

  1. Andrews, G. E. (1976). The Theory of Partitions . Addison-Wesley Publishing Company.
  2. 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) .
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. Gent, I. P. (1998). Heuristic solution of open bin packing problems. Journal of Heuristics , 3 (4), 299-304.
  9. 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

See all 49

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
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.