Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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)

share|improve this answer
    
Ah—awesome! Thanks :) –  Magnus Lie Hetland Feb 8 '12 at 12:44
1  
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. –  Magnus Lie Hetland Feb 8 '12 at 14:33
1  
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. –  Chandra Chekuri Feb 13 '12 at 1:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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