1
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ If $S_i$ is a set of sets, have you tried to prove it NP-hard? What partner problems have you looked at? $\endgroup$ – D.W.♦ Nov 1 '19 at 17:59
  • $\begingroup$ @D.W. See my edits $\endgroup$ – zdm Nov 2 '19 at 1:23
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Nov 2 '19 at 1:43
  • $\begingroup$ 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$. $\endgroup$ – zdm Nov 2 '19 at 2:03
  • $\begingroup$ That doesn't match your first example. $\endgroup$ – D.W.♦ Nov 2 '19 at 2:04
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks, very interesting! For what values of $c_i$, is it still NP-hard? If $c_i=2$? $\endgroup$ – zdm Nov 2 '19 at 5:27
  • $\begingroup$ @zdm It is still NP-hard by a reduction from Rainbow Matching. $\endgroup$ – xskxzr Nov 2 '19 at 6:39
  • $\begingroup$ So, can we say that exact cover problem is NP-hard even if each subset has size at most 2? $\endgroup$ – zdm Nov 4 '19 at 14:22
  • $\begingroup$ 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. $\endgroup$ – zdm Nov 4 '19 at 14:49
  • $\begingroup$ 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. $\endgroup$ – xskxzr Nov 4 '19 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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