# Does this bin packing problem have a name?

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.

• 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. Feb 13 '12 at 1:03