# Approximating Bin Packing within O(log OPT * log log OPT) bins

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jan 2013.

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

- [Online Bin Packing with Predictions](https://mlsanity.com/paper/2102.03311/) (2021)
- [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 s_1,...,s_n in [0,1] which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar-Karp algorithm from '82 produces a solution with at most OPT + O(log^2 OPT) bins. We provide the first improvement in now 3 decades and show that one can find a solution of cost OPT + O(log OPT * log log OPT) in polynomial time. This is achieved by rounding a fractional solution to the Gilmore-Gomory LP relaxation using the Entropy Method from discrepancy theory. The result is constructive via algorithms of Bansal and Lovett-Meka.