Reputation: 11
The general bin-packing problem is NP complete.
I have read several papers and other source but I am still not clear about whether a bin-packing problem with a fixed number of bins is NP-hard.
Wikipedia says: "Computationally, the problem is NP-hard, and the corresponding decision problem, deciding if items can fit into a specified number of bins, is NP-complete."
and later: "On the other hand, bin packing is solvable in pseudo-polynomial time for any fixed number of bins K, and solvable in polynomial time for any fixed bin capacity B."
In another paper "Bin packing with fixed number of bins revisited" I have read that for a fixed number of bins, if the sizes of the items are polynomially bounded integers, then the problem can be solved in time n^(O(k)).
My specific problem is the following. I have a fixed number of bins m with fixed capacity. The items arrive online. I one case the set of items is known in the other case it is not.
Given on what I have read I assume this problem is not NP hard as it could be solved by exhaustive search.
Upvotes: 1
Views: 133