# A Logarithmic Additive Integrality Gap for Bin Packing

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2015.

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

- [Online Bin Packing with Predictions](https://mlsanity.com/paper/2102.03311/) (2021)
- [Budgeted Online Model Selection and Fine-Tuning via Federated Learning](https://mlsanity.com/paper/2401.10478/) (2024)
- [Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical](https://mlsanity.com/paper/2209.01147/) (2022)

## Abstract (arXiv)

For bin packing, the input consists of n items with sizes s1,...,sn ∈ [0,1] which have to be assigned to a minimum number of bins of size 1. Recently, the second author gave an LP-based polynomial time algorithm that employed techniques from discrepancy theory to find a solution using at most OPT + O(log OPT · log log OPT) bins. In this paper, we present an approximation algorithm that has an additive gap of only O(log OPT) bins, which matches certain combinatorial lower bounds. Any further improvement would have to use more algebraic structure. Our improvement is based on a combination of discrepancy theory techniques and a novel 2-stage packing: first we pack items into containers; then we pack containers into bins of size 1. Apart from being more effective, we believe our algorithm is much cleaner than the one of Rothvoss.