# Online Bin Packing with Predictions

arXiv: https://arxiv.org/abs/2102.03311 · HTML: https://mlsanity.com/paper/2102.03311/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 85 references that are in the map.
- First posted on arXiv 5 Feb 2021.

## Builds on (most cited first, 16 of 16)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Online 3D Bin Packing with Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/2006.14978/) (2020)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Overcommitment in Cloud Services -- Bin packing with Chance Constraints](https://mlsanity.com/paper/1705.09335/) (2017)
- [A Logarithmic Additive Integrality Gap for Bin Packing](https://mlsanity.com/paper/1503.08796/) (2015)
- [Approximating Bin Packing within O(log OPT * log log OPT) bins](https://mlsanity.com/paper/1301.4010/) (2013)
- [Optimal Rectangle Packing: An Absolute Placement Approach](https://mlsanity.com/paper/1402.0557/) (2014)
- [Randomization can be as helpful as a glimpse of the future in online computation](https://mlsanity.com/paper/1511.05886/) (2015)
- [A new and improved algorithm for online bin packing](https://mlsanity.com/paper/1707.01728/) (2017)
- [A new lower bound for classic online bin packing](https://mlsanity.com/paper/1807.05554/) (2018)

## Built on by (most cited first, 11 of 11)

- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets](https://mlsanity.com/paper/2211.06567/) (2022)
- [Generalizable Heuristic Generation Through LLMs with Meta-Optimization](https://mlsanity.com/paper/2505.20881/) (2025)
- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Robust Learning-Augmented Dictionaries](https://mlsanity.com/paper/2402.09687/) (2024)
- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [(X)-evolve: Solution space evolution powered by large language models](https://mlsanity.com/paper/2508.07932/) (2025)
- [Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems](https://mlsanity.com/paper/2406.18752/) (2024)
- [Online Search With Best-Price and Query-Based Predictions](https://mlsanity.com/paper/2112.01592/) (2021)
- [Pattern based learning and optimisation through pricing for bin packing problem](https://mlsanity.com/paper/2409.04456/) (2024)
- [Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management](https://mlsanity.com/paper/2604.26349/) (2026)

## Abstract (arXiv)

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 under competitive analysis, 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.