Summary: 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)\cdot 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\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.