Bin packing with fixed number of bins revisited

As Bin Packing is NP-hard already for k=2k=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)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)f(k)⋅nO(1) for any function f(k)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)2O(klog2k)+O(n) a solution with additive error at most 1, i.e., either finds a packing into k+1k+1 bins or decides that k bins do not suffice.

► We present an approximation algorithm for bin packing with additive error 1.
► The running time of our algorithm is linear in the number of items and single-exponential in the number of bins.
► We prove that (even the unary version of) bin packing is W[1]-hard parameterized by the number of bins.
► Conclusion: the number of bins has to appear in the exponent of the input size in any exact algorithm (unless W[1] = FPT).