# Multiple Knapsack Problem with Set of Admissible Balls

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

• 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.
– zdm
Nov 5 '19 at 0:27
• I have mentioned that Rainbow Matching can be reduced to this problem. Where do you get stuck? Nov 5 '19 at 2:04
• @D.W. Please see my edits. Is it clearer now.
– zdm
Nov 5 '19 at 5:42
• @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?
– zdm
Nov 5 '19 at 5:55

## 1 Answer

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.

• 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?
– zdm
Nov 5 '19 at 5:39
• 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.)
– zdm
Nov 5 '19 at 16:49
• 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). Nov 6 '19 at 1:34
• 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. Nov 6 '19 at 1:44
• 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. Nov 8 '19 at 1:47