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°(k) for an input of length n by dynamic programming. We show, by proving the W[l]-hardness of Unary Bin Packing (where the sizes are given in unary encoding), that this running time cannot be improved to f{k) . n0(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°(k log~2 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.