Iterated-Logarithmic Additive Hardness for Bin Packing

A new proof establishes that, unless P=NP, no deterministic polynomial-time bin-packing algorithm can guarantee a packing using at most OPT + c·log*OPT bins for some absolute constant c>0, ruling out any additive error of o(log*OPT). The result addresses the third of ten open problems posed in Williamson and Shmoys' "The Design of Approximation Algorithms" and improves on OpenAI's earlier [Ope26] hardness showing that no deterministic polynomial-time algorithm achieves OPT + O(1) bins. The best known upper bound remains OPT + O(log OPT), from Hoberg and Rothvoss [HR17], a randomized algorithm with expected polynomial running time; the authors conjecture the optimal additive error is Θ(log OPT).

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} $.