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?.

Improve this question
$\endgroup$
4
  • $\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$ Commented Nov 5, 2019 at 0:27
  • 1
    $\begingroup$ I have mentioned that Rainbow Matching can be reduced to this problem. Where do you get stuck? $\endgroup$ Commented Nov 5, 2019 at 2:04
  • $\begingroup$ @D.W. Please see my edits. Is it clearer now. $\endgroup$ Commented Nov 5, 2019 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$ Commented Nov 5, 2019 at 5:55

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
9
  • $\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$ Commented Nov 5, 2019 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$ Commented Nov 5, 2019 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$ Commented Nov 6, 2019 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$ Commented Nov 6, 2019 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$ Commented Nov 8, 2019 at 1:47

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.