Balls in monochromatic bins

Question

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

Answer 1

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.