A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing

Klaus Jansen, Felix Ohnesorge, Lis Pirotton

Consider a high-multiplicity Bin Packing instance $I$ with $d$ distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime ${{|I|}^2}^{O(d)}$ for this problem…