← 研踪 PaperTrailarXiv:2611.09447 · v1
Additive $Ω(\log^* OPT)$ Gap for Bin Packing with Three Items per Bin
首次提交 2026-11-06 21:20
版本更新 2026-11-06 21:20
雷达观测 2026-11-09 11:19
摘要
We prove that bin packing is NP-hard to approximate within an additive factor of $o(\ls\OPT)$, even when all item sizes are arbitrarily close to . This gives the first lower bound for bin packing with an additive factor that depends explicitly on the optimum value. In addition, we give a polynomial-time reduction from any bin packing instance into one with item sizes arbitrarily close to , preserving its additive configuration-LP gap up to constant factors. Thus, 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 $Ω(\ls\OPT)$ gap for 3-partition instances. We build on the recent OpenAI construction that uses five items per bin and rules out any constant additive gap.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-06 21:20 · 最新观测版本
Additive $Ω(\log^* OPT)$ Gap for Bin Packing with Three Items per Bin
We prove that bin packing is NP-hard to approximate within an additive factor of $o(\ls\OPT)$, even when all item sizes are arbitrarily close to . This gives the first lower bound for bin packing with an additive factor that depends explicitly on the optimum value. In addition, we give a polynomial-time reduction from any bin packing instance into one with item sizes arbitrarily close to , preserving its additive configuration-LP gap up to constant factors. Thus, 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 $Ω(\ls\OPT)$ gap for 3-partition instances. We build on the recent OpenAI construction that uses five items per bin and rules out any constant additive gap.
查看此版本解读 →查看此版本原文 ↗