Editing Bin packing problem (section)

=== Additive approximation ===
The [[Karmarkar-Karp bin packing algorithms|Karmarkar-Karp bin packing algorithm]] finds a solution with size at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(\mathrm{OPT}))</math>, and runs in time polynomial in {{mvar |n}} (the polynomial has a high degree, at least 8).

Rothvoss<ref name=":2">{{Cite book |last=Rothvoß |first=T. |chapter=Approximating Bin Packing within O(log OPT · Log Log OPT) Bins |date=2013-10-01 |chapter-url=https://ieeexplore.ieee.org/document/6686137 |title=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |pages=20–29 |arxiv=1301.4010 |doi=10.1109/FOCS.2013.11 |isbn=978-0-7695-5135-7 |s2cid=15905063}}</ref> presented an algorithm that generates a solution with at most <math>\mathrm{OPT} + \mathcal{O}(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))</math> bins.

Hoberg and Rothvoss<ref name=":3">{{Citation |last1=Hoberg |first1=Rebecca |last2=Rothvoss |first2=Thomas |date=2017 |chapter=A Logarithmic Additive Integrality Gap for Bin Packing |title=Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms |publisher=SIAM |pages=2616–2625 |arxiv=1503.08796 |doi=10.1137/1.9781611974782.172 |isbn=978-1-61197-478-2 |doi-access=free |s2cid=1647463}}</ref> improved this algorithm to generate a solution with at most <math>\mathrm{OPT} + \mathcal{O}(\log(\mathrm{OPT}))</math> bins. The algorithm is randomized, and its running-time is polynomial in {{mvar |n}}.