2
$\begingroup$

Citing "Computers and Intractability" book by Michael R. Garey and David S. Johnson, the bin packing problem is defined as:

INSTANCE. Finite set $U$ of items, a size $s(u) \in Z$ for each $u \in U$, a positive integer bin capacity $B$, and a positive integer $K$.

QUESTION. Is there a partition of $U$ into disjoint sets $U_1, U_2, ..., U_k$ such that the sum of sizes of the items in each $U_i$ is $B$ or less?

$Comment$: (...) Solvable in polynomial time for any fixed $B$ by exhaustive search.

Now, my question is to that comment. How does the NP-completeness breaks for fixed $B$ ? I know that, e.g., for fixed number of bins there is a pseudo-polynomial time algorithm ( Bin packing with fixed number of bins revisited, Klaus Jansen et al.), but I don't see how it translates the the fixed bin size.

Bin size constraint sets an upper bound on maximum item size, and because sizes are integers therefore there is fixed number of possible sizes. But still, it seems to me that there are more like $O(n!)$ number of possible bin assignments - or am I wrong?

$\endgroup$
0
$\begingroup$

Let $p(B)$ be the number of partitions of $B$ into an unordered sum of positive integers. It suffices to check the $k^{p(0)+p(1)+\dots+p(B)}$ possible ways to assign a number of bins to each partition (count the number of bins having each type of partition).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.