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 n(O(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) . n(O(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 2(O(k log2 k)) + 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. (c) 2012 Elsevier Inc. All rights reserved.
bin packing parameterized complexity additive approximation will-hardness