Bin packing with fixed number of bins revisited

摘要

As Bin Packing is NP-hard already for k=2 bins, it is unlikely to be solvable in polynomial time even if the number of bins is a fixed constant. However, if the sizes of the items are polynomially bounded integers, then the problem can be solved in time nO(k) for an input of length n by dynamic programming. We show, by proving the W[1]-hardness of Unary Bin Packing (where the sizes are given in unary encoding), that this running time cannot be improved to f(k)⋅nO(1) for any function f(k) (under standard complexity assumptions). On the other hand, we provide an algorithm for Bin Packing that obtains in time 2O(klog2k)+O(n) a solution with additive error at most 1, i.e., either finds a packing into k+1 bins or decides that k bins do not suffice.