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
Mitzenmacher, M., & Vassilvitskii, S. (2022) · Communications of the ACM · doi:10.1145/3528087 · Cited by 280
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
Adaptive Resource Provisioning for the Cloud Using Online Bin Packing
Song, W., Xiao, Z., Chen, Q., & Luo, H. (2014) · IEEE Transactions on Computers · doi:10.1109/tc.2013.148 · Cited by 233
The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
Dósa, G. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74450-4_1 · Cited by 220
Online 3D Bin Packing with Constrained Deep Reinforcement Learning
Zhao, H., She, Q., Zhu, C., Yang, Y., & Xu, K. M. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i1.16155 · Cited by 216
On Packing Two-Dimensional Bins
Chung, F., Garey, M. R., & Johnson, D. S. (1982) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0603007 · Cited by 211
Near-Optimal Bounds for Online Caching with Machine Learned Advice
Rohatgi, D. (2020) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975994.112 · Cited by 198
Heuristics for the integer one-dimensional cutting stock problem: A computational study
W�scher, G., & Gau, T. (1996) · OR Spectrum · doi:10.1007/bf01539705 · Cited by 189
Competitive Caching with Machine Learned Advice
Lykouris, T., & Vassilvitskii, S. (2021) · Journal of the ACM · doi:10.1145/3447579 · Cited by 172
Online Algorithms for Rent-Or-Buy with Expert Advice.
Gollapudi, S., & Panigrahi, D. (2019) · International Conference on Machine Learning · Cited by 169
Allocating online advertisement space with unreliable estimates
Mahdian, M., Nazerzadeh, H., & Saberi, A. (2007) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1250910.1250952 · Cited by 148
Online Scheduling via Learned Weights
Lattanzi, S., Lavastida, T., Moseley, B., & Vassilvitskii, S. (2019) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975994.114 · Cited by 128
A short note on learning discrete distributionsPreprint
Canonne, C. L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.11457 · Cited by 128
A new algorithm for optimal bin packing
Korf, R. E. (2002) · Cited by 124
Online Metric Algorithms with Untrusted Predictions
Antoniadis, A., Coester, C., Eliáš, M., Polak, A., & Simon, B. (2023) · ACM Transactions on Algorithms · doi:10.1145/3582689 · Cited by 124
Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online AlgorithmsPreprint
Wei, A., & Zhang, F. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.11443 · Cited by 112
Improving Online Algorithms via ML Predictions
Kumar, R., Purohit, M., & Svitkina, Z. (2024) · arXiv · doi:10.48550/arxiv.2407.17712 · Cited by 111
The Bin‐Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP
Schwerin, P., & Wäscher, G. (1997) · International Transactions in Operational Research · doi:10.1111/j.1475-3995.1997.tb00093.x · Cited by 101
A New and Improved Algorithm for Online Bin Packing
Balogh, J., Békési, J., Dósa, G., Epstein, L., & Levin, A. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.esa.2018.5 · Cited by 99
BPPLIB: a library for bin packing and cutting stock problems
Delorme, M., Iori, M., & Martello, S. (2017) · Optimization Letters · doi:10.1007/s11590-017-1192-z · Cited by 98
A Logarithmic Additive Integrality Gap for Bin Packing
Hoberg, R., & Rothvoß, T. (2017) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974782.172 · Cited by 95
Online Knapsack with Frequency Predictions
Im, S., Kumar, R., Qaem, M. M., & Purohit, M. (2021) · neural information processing systems · Cited by 88
Secretary and online matching problems with machine learned advice
Antoniadis, A., Gouleakis, T., Kleer, P., & Kolev, P. (2023) · Discrete Optimization · doi:10.1016/j.disopt.2023.100778 · Cited by 85
Online Optimization with Uncertain Information
Mahdian, M., Nazerzadeh, H., & Saberi, A. (2012) · ACM Transactions on Algorithms · doi:10.1145/2071379.2071381 · Cited by 80
Dual Inequalities for Stabilized Column Generation Revisited
Gschwind, T., & Irnich, S. (2016) · INFORMS journal on computing · doi:10.1287/ijoc.2015.0670 · Cited by 79
Bin Completion Algorithms for Multicontainer Packing, Knapsack, and Covering Problems
Fukunaga, A. S., & Korf, R. E. (2007) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2106 · Cited by 77
Online 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-citationLearnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
Lavastida, T., Moseley, B., Ravi, R., & Xu, C. (2020) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.esa.2021.59 · Cited by 72
Optimal Rectangle Packing: An Absolute Placement Approach
Huang, E., & Korf, R. E. (2013) · Journal of Artificial Intelligence Research · doi:10.1613/jair.3735 · Cited by 71
Online Bin Packing with Advice
Boyar, J., Kamali, S., Larsen, K. S., & López-Ortíz, A. (2014) · Algorithmica · doi:10.1007/s00453-014-9955-8 · Cited by 64
Self-citationApproximating Bin Packing within O(log OPT · Log Log OPT) Bins
Rothvoß, T. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.11 · Cited by 63
Tight bounds for online vector bin packing
Azar, Y., Cohen, I. R., Kamara, S., & Shepherd, F. B. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488730 · Cited by 59
Online Weighted Matching with a Sample
Kaplan, H. Y., Naori, D., & Raz, D. (2022) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977073.52 · Cited by 50
An Improved Algorithm for Optimal Bin Packing
Korf, R. E. (2003) · Cited by 44
On Line Bin Packing with Items of Random Size
Rhee, W. T., & Talagrand, M. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.2.438 · Cited by 38
Cloud Storage and Online Bin Packing
Bein, D., Bein, W. W., & Venigella, S. (2011) · Studies in computational intelligence · doi:10.1007/978-3-642-24013-3_7 · Cited by 35
Interior-Point-Based Online Stochastic Bin Packing
Gupta, V., & Radovanović, A. (2020) · Operations Research · doi:10.1287/opre.2019.1914 · Cited by 31
Uniform Loss Algorithms for Online Stochastic Decision-Making With Applications to Bin Packing
Banerjee, S., & Freund, D. (2020) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/3393691.3394224 · Cited by 28
Improved bin completion for optimal bin packing and number partitioning
Schreiber, E. L., & Korf, R. E. (2013) · Cited by 23
Customizing ML Predictions for Online AlgorithmsPreprint
Anand, K., Ge, R., & Panigrahi, D. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2205.08715 · Cited by 23
Improving Online Rent-or-Buy Algorithms with Sequential Decision Making and ML Predictions
Banerjee, S. (2020) · neural information processing systems · Cited by 23
On number of partitions of an integer into a fixed number of positive integers
Oruç, A. Y. (2015) · Journal of Number Theory · doi:10.1016/j.jnt.2015.06.023 · Cited by 22
Overcommitment in Cloud Services Bin packing with Chance Constraints
Cohen, M. C., Keller, P. W., Mirrokni, V., & Zadimoghaddam, M. (2017) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/3078505.3078530 · Cited by 21
Randomization can be as helpful as a glimpse of the future in online computationPreprint
Mikkelsen, J. W. (2015) · arXiv (Cornell University) · doi:10.4230/lipics.esa.2016.37 · Cited by 19
Online Bin Packing with Advice of Small Size
Angelopoulos, S., Dürr, C., Kamali, S., Renault, M. P., & Rosén, A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-21840-3_4 · Cited by 18
Self-citationWeibull-Based Benchmarks for Bin Packing
Castiñeiras, I., De Cauwer, M., & O’Sullivan, B. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33558-7_17 · Cited by 14
All-Around Near-Optimal Solutions for the Online Bin Packing Problem
Kamali, S., & López-Ortíz, A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48971-0_61 · Cited by 11
Self-citation
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 69
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
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.