2025/12/02 by Klaus Jansen, Ohnesorge, Felix, Jansen, Klaus +3 · 1 citation
Engineering · Computer Science · #Optimization and Packing Problems #Complexity and Algorithms in Graphs #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2512.02758
Consider the classical Bin Packing problem with d different item sizes si and amounts of items ai. 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Ω(d). Our lower bound matches the upper bound of 2d 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.