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. © 2012 Elsevier Inc