Paper 2026/2644

Iterated-Logarithmic Additive Hardness for Bin Packing

Abstract

The question of obtaining a constant-additive approximation for bin packing was highlighted in the third of ten open problems in Williamson and Shmoys' The Design of Approximation Algorithms [SW11, Chapter~17, Problem~3]. We prove that there is an absolute constant $c>0$ such that, unless $\mathrm P=\mathrm{NP}$, no deterministic polynomial-time packing using at most $\mathrm{OPT}+c\log^*\mathrm{OPT}$ bins, where $\mathrm{OPT}$ is the minimum number of bins. In particular, no such algorithm has additive error $o(\log^*\mathrm{OPT})$. The best known upper bound, due to Hoberg and Rothvoss [HR17], is $\mathrm{OPT}+O(\log\mathrm{OPT})$, achieved by a randomized algorithm with expected polynomial running time. OpenAI [Ope26] previously showed that, unless $\mathrm P=\mathrm{NP}$, no deterministic polynomial-time algorithm guarantees a packing using at most $\mathrm{OPT}+O(1)$ bins. We conjecture that the optimal additive approximation error for bin packing is $\Theta(\log \mathrm{OPT})$.