2
$\begingroup$

Suppose we have a collection of $m$ balls in $k$ different colors. Let $b_i$ be the number of balls with color $i$, so $\sum_{i=1}^k b_i = m$. Assume we have $n$ bins with capacities $c_1, \dots, c_n$, such that $\sum_{j=1}^n c_j \geq m$.

We say an assignment of balls into bins is monochromatic if it satisfies three conditions:

(I) Each ball is assigned to exactly one bin.

(II) Number of balls assigned to a bin is at most its capacity.

(III) A bin is either empty or monochromatic, i.e. it does NOT contain two balls with different colors.

Question: How do we decide for a given collection of $m$ balls with $k$ colors, and $n$ bins with capacities, whether there is a monochromatic assignment? Is this problem $NP$-hard?

For example if we have two balls $b_1=7, b_2=3$, then it is impossible to distribute them to two bins with capacities $c_1=5, c_2=6$, but we can distribute them into three bins with capacities $c_1=5, c_2=2, c_3=3$.

$\endgroup$

1 Answer 1

4
$\begingroup$

It is NP-hard, by reduction from multiway number partitioning: given an instance of multiway number partitioning, i.e., a multiset $S$ and a target $T$ and a positive integer $k$ so that $S$ sums to $kT$, set $b_1=\dots=b_k=T$ and $c_1,\dots,c_n$ the multiset. Then there is a monochromatic assignment iff there is a valid solution to the multiway number partitioning problem.

$\endgroup$
1
  • $\begingroup$ Smart reduction :-) $\endgroup$
    – AAArAAA
    Mar 22, 2023 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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