0
$\begingroup$

I was thinking about variants of bin packing and thought of this variant wherein the given $m$ bins have size specified(not necessarily same) and we need to put $n$ objects in them. Is this still NP Hard, considering that bin packing is NP hard?

$\endgroup$
2
$\begingroup$

Yes, it's still NP-hard, because the input could specify that the bins actually are the same size, which is the standard NP-hard version.

A general rule of thumb is that allowing the input to be more general can't make the problem any easier, as long as the new setting includes the original hard case as a special case.

$\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.