The Support of Bin Packing is Exponential

Consider the classical Bin Packing problem with d different item sizes s_i and amounts of items a_i. The support of a Bin Packing solution is the number of differently filled bins. In this work, we show that the lower bound on the support of this problem is 2 to the power of Omega of d. Our lower bound  matches the upper bound of 2 to the power of d given by Eisenbrand and Shmonin [Oper.Research Letters '06] up to a constant factor.

This result has direct implications for the time complexity of several Bin Packing algorithms, such as Goemans and Rothvoss [SODA '14], Jansen and Klein [SODA '17] and Jansen and Solis-Oba [IPCO '10].

To achieve our main result, we develop a technique to aggregate equality constrained ILPs with many constraints into an equivalent ILP with one constraint. Our technique contrasts existing aggregation techniques as we manage to integrate upper bounds on variables into the resulting constraint. We believe this technique can be useful for solving general ILPs or the d-dimensional knapsack problem.

Preview

Logo BII

Rights

Use and reproduction:


CC BY 4.0

Please note that individual components of the publication may be subject to other licensing or copyright conditions.

Cite

Citation style:
Could not load citation form.