7
$\begingroup$

My problem is related to the standard bin packing problem (where you have bins of capacity $1$, items of capacity $(0,1]$, and want to pack the items into as few bins as possible), but there are a couple of twists. First, you have a fixed number of bins, and want to fit as many items as possible into them. As far as I can see, this is not obviously equivalent (except for the decision versions of the problems). Or perhaps I’m missing something obvious?

Second, some items are not permitted in some bins. That is, for each item, there is a list of forbidden bins.

Does this problem have a name? Even a name for the version without the forbidden bins would be useful. (I’m sure the “as many items as possible” part must be a totally standard packing problem?)

What I’m ultimately looking for is a way of attacking the problem (an exponential, exact DP algorithm; an approximation algorithm; a good heuristic/B&B solution…), or some starting-point that could be adapted.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Your problem is the multiple knapsack problem.

Although I am not familiar with this problem, I believe you'll find some papers on your problem, since there are many papers on this problem (see for example a SODA 2009 paper)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It actually seems that the full problem (with the restrictions) is a standard problem, too. Kellerer et al. (Knapsack Problems, Springer, 2004) call it the multiple knapsack problem with assignment restrictions. There’s even a name for the unit cost verison (i.e., the one I’m dealin with): Multiple subset sum problem with assignment restrictions. There’s even a publication on approximations for it by Dawande et al. $\endgroup$
    – Magnus Lie Hetland
    Commented Feb 8, 2012 at 14:33
  • 1
    $\begingroup$ There is an even further generalization called the generalized assignment problem (the maximization version) where the size of an item depends on the bin it is assigned to and so does the profit. There is a $(1-1/e-\delta)$-approximation for this problem for some tiny $\delta$ but the $(1-1/e)$-approximation is some what clean and nice. $\endgroup$
    – Chandra Chekuri
    Commented Feb 13, 2012 at 1:03

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.