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

Question

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?

Answer 1

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.