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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jun 14, 2016 at 7:25