0
$\begingroup$

We have $m$ bins and $n$ balls.

  1. Each bin $i=1,2,\ldots,m$ can contain at most two balls (not any two balls but two balls from some specific set), see 3.
  2. Each ball $j=1,2,\ldots,n$ can be put into bin $i=1,2,\ldots,m$.
  3. For each bin $i=1,2,\ldots,m$, there is a collection of sets $S_i=\{X_1,X_2,\ldots,X_{k_i}\}$ for given $k_i$ ($k_i\geq0$ and $k_i\leq\binom{n}{2}$). Each $X_j\in S_i$ is a 2-cardinality set and it represents the set of two balls that can be put into bin $i$. We can only choose at most one set from $S_i$.

For example, for $m=2$ and $n=3$. Say we have $k_1=0$ and $k_2=2$ and $S_1=\emptyset$. $S_2=\{\{1,2\},\{2,3\}\}$. This means that:

  1. Ball $1$, $2$ or $3$ can be each put into bin $1$ or bin $2$. This is always true (for all instances of the problem).
  2. In bin $1$, we cannot put any set of two balls.
  3. In bin $2$, we can put balls $1$ and $2$ or balls $2$ and $3$.

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

Since, we have the assumption that $|X_j|=2$, I was thinking that maybe we can solve it in polynomial-time. I am trying to prove that it is easy by reducing it to maximum flow.

A problem similar to this one but more general was posted here Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?.

$\endgroup$
  • $\begingroup$ if $S_i$ is empty, that means we can put at most one ball in bin $i$. If $S_i$ is not empty, say $S_i=\{\{1,2\},\{2,3\}\}$, then in bin $i$ we can put either a single ball or balls 1 and 2 or balls 2 and 3. $\endgroup$ – zdm Nov 5 at 0:27
  • 1
    $\begingroup$ I have mentioned that Rainbow Matching can be reduced to this problem. Where do you get stuck? $\endgroup$ – xskxzr Nov 5 at 2:04
  • $\begingroup$ @D.W. Please see my edits. Is it clearer now. $\endgroup$ – zdm Nov 5 at 5:42
  • $\begingroup$ @xskxzr The problem with Rainbow Matching is that we have to find a set of pairwise non-adjacent edges. In my problem, we may match two balls with a single bin, is that makes the edges adjacent? $\endgroup$ – zdm Nov 5 at 5:55
2
$\begingroup$

This is NP-hard by reduction from 3-dimensional matching (3DM): turn each triple $\{a, b, c\}$ into a valid pair $\{a, b\}$ of balls for bin $c$, and add a large number of balls that don't belong to any valid pairs (so that if they go in a bin, they must be the sole occupant). The optimal solution will then hold $k+m$ balls ($k$ bins with 2 balls each and $m-k$ bins with 1 ball each), where $k$ is the largest size of any 3DM for the original input.

$\endgroup$
  • $\begingroup$ My understanding with "... add a large number of balls that do not belong to any valid pairs", is that we cannot put ball $a$ or ball $b$ in bin $c$. But in the definition of the problem, any single ball can be put in any bin. am I wrong? $\endgroup$ – zdm Nov 5 at 5:39
  • $\begingroup$ We can also use 3DM with $|X|=|Y|=|Z|=m$ and we create an instance with $2m$ balls. We can say that there is a 3DM matching of size $m$ iff the optimal solution to the problem is $2m$. Is this correct? (I mean, I tried to not add a large number of balls.) $\endgroup$ – zdm Nov 5 at 16:49
  • $\begingroup$ I'm afraid I don't understand your first comment, could you word it another way? I meant that we create a ball for each distinct value appearing in the first position of each triple, and likewise for the second position of each triple, and each triple allows a given pair of balls to be put together into a given bin, and then in addition to those balls add a bunch more balls, which are not allowed to be put in the same bin as any other ball and serve only to (half-)fill any remaining bins so that we can always know exactly how many bins are "full" (have 2 balls). $\endgroup$ – j_random_hacker Nov 6 at 1:34
  • $\begingroup$ Regarding your second comment, I believe that is correct, but it's not enough for a reduction from the (decision form of the) full 3DM problem, since (AFAIK) that problem takes an additional threshold parameter $k$ as part of its input, being the size of the 3DM we want to test for, and this is allowed to differ from $m$. But I think this is not a problem -- when $k \ne m$, I think there should always be enough balls to half-fill any remaining bins (i.e. no bin will be left empty) without having to add any more in, which means we can still determine $k$ from the number of balls in a solution. $\endgroup$ – j_random_hacker Nov 6 at 1:44
  • 1
    $\begingroup$ Suppose there are 4 balls $a, b, c, d$, bin 1 allows ball pairs $\{a, b\}$ and $\{c, d\}$, while bin 2 allows just ball pair $\{a, b\}$. If you try adding ball pair $\{a, b\}$ to bin 1 first, you find that they fit, but that you then can't get any further -- even though a solution does exist in which you hold off adding $\{a, b\}$ until you get to bin 2. $\endgroup$ – j_random_hacker Nov 8 at 1:47

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.