We show that bin packing remains NP‑hard to approximate within an additive factor of $o(\log^* \text{OPT})$ even when every item size can be made arbitrarily close to $1/3$. This provides the first lower bound whose additive term depends explicitly on the optimum value. Moreover, we present a polynomial‑time reduction that transforms any bin‑packing instance into one whose item sizes are nearly $1/3$, while preserving the additive configuration‑LP gap up to constant factors. Consequently, in the sense of additive configuration‑LP gap and up to a constant, we confirm the conjecture that 3‑partition instances are the hardest bin‑packing instances. In particular, we obtain an unconditional $\Omega(\log^* \text{OPT})$ gap for 3‑partition instances. Our work builds on the recent OpenAI construction that uses five items per bin and rules out any constant additive gap.
Review: This breakthrough introduces the iterated logarithm of the optimum into the additive hardness of bin packing, solidifying the pivotal role of 3‑partition in the problem’s approximation landscape.