1
$\begingroup$

I was wondering if a variation of the bin packing problem where the 'size' of a bin is calculated as the product of item sizes in a bin instead of their sum is NP-hard. It seems like it must be, but I don't know how to prove it.

More formally, the problem is as follows:

Given a list of positive integer item sizes $a_1, a_2, ..., a_n$ and a positive integer $x$, find the smallest positive integer $k$ such that it is possible to partition the items into $k$ disjoint sets $S_1, S_2, ..., S_k$ such that the product of sizes in each $S_i$ is $\leq x$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The bin packing problem is strongly NP-hard. That means that even if the sizes are given in unary, the problem is still NP-hard.

In your case, your product-bin packing is equivalent to sum-bin packing, using $\log a_i$ and $\log x$ as sizes, and it is still NP-hard.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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