# Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?

Let us say we have $$m$$ bins and $$n$$ balls. Every bin $$i$$ has capacity $$c_i$$ which is the number of balls that can be put into bin $$i$$. We have $$c_i\geq1$$ for all $$i$$. For each bin $$i$$, there is a collection of sets $$S_i=\{X_1,X_2,\ldots,X_{k_i}\}$$ for given $$k_i$$. Each $$X_j\in S_i$$ is the set of balls that can be put into bin $$i$$. We have $$|X_j|\leq c_i$$ and $$\emptyset\in S_i$$ for all $$i$$.

For example, for $$m=2$$ and $$n=3$$, with $$c_1=1$$ and $$c_2=2$$, say we have $$k_1=4$$ and $$k_2=5$$. Say we have $$S_1=\{\emptyset,\{1\},\{2\},\{3\}\}$$. $$S_2=\{\emptyset,\{1\},\{2\},\{3\},\{2,3\}\}$$. This means that ball $$1$$, $$2$$ or $$3$$ can be each assigned to bin $$1$$. Also, each ball can be assigned to bin $$2$$. Further, balls $$2$$ and $$3$$ can be together assigned to bin $$2$$. We might have an instance with $$k_2=6$$ and $$S_2=\{\emptyset,\{1\},\{2\},\{3\},\{2,3\},\{1,2\}\}$$ for example.

We want to assign the maximum number of balls into the bins. Is this easy or hard?

• If $S_i$ is a set of sets, have you tried to prove it NP-hard? What partner problems have you looked at?
– D.W.
Nov 1 '19 at 17:59
• @D.W. See my edits
– zdm
Nov 2 '19 at 1:23
• I'm still not clear on what the problem statement is. I'd still like to see a general specification of what assignments are legal, and how this relates to the $S_i$. Two examples are not a substitute for a general specification. Also, are you sure you mean $\{\{2,3\}\}$ and not $\{\{2\},\{3\}\}$? (Yet another reason we need a general specification.) I don't know what $c_i$-admissible or 2-admissible means; please define all non-standard terminology. Also, I still don't see any indication of what you have tried or whether you have tried to prove the problem NP-hard and if so how.
– D.W.
Nov 2 '19 at 1:43
• If $S_i=\{X_1, X_2, \ldots, X_{k_i}\}$, then each $X_j$ is a set of balls that can be put together into bin $i$.
– zdm
Nov 2 '19 at 2:03
• That doesn't match your first example.
– D.W.
Nov 2 '19 at 2:04

You can reduce the Exact Cover problem to your problem. The elements in the Exact Cover problem corresponds to the balls in your problem. For each subset $$T$$ in the Exact Cover problem, we construct a bin $$i$$ with $$S_i=\{\emptyset, T\}$$. Then there exists an exact cover if and only if all balls can be put into the bins. Hence, your problem is NP-hard.

• Thanks, very interesting! For what values of $c_i$, is it still NP-hard? If $c_i=2$?
– zdm
Nov 2 '19 at 5:27
• @zdm It is still NP-hard by a reduction from Rainbow Matching. Nov 2 '19 at 6:39
• So, can we say that exact cover problem is NP-hard even if each subset has size at most 2?
– zdm
Nov 4 '19 at 14:22
• If we add the constraint that if $X_j\in S_i$ then all subsets of $X_j$ are also in $S_i$, can we still prove NP-hardness? If balls $\{2,3\}$ can be put into bin $i$ then ball $2$ can be put alone and also ball $3$ can be put alone.
– zdm
Nov 4 '19 at 14:49
• The hardness of this problem comes from the constraint that you can only select one set from $S_i$. Exact 2-set cover has no such constraint. Comments are not for extended disccusion, you can ask a new question. Nov 4 '19 at 16:40