<p>It is NP-hard, by reduction from <a href="https://en.wikipedia.org/wiki/Multiway_number_partitioning" rel="nofollow noreferrer">multiway number partitioning</a>: given an instance of multiway number partitioning, i.e., a multiset <span class="math-container">$S$</span> and a target <span class="math-container">$T$</span> and a positive integer <span class="math-container">$k$</span> so that <span class="math-container">$S$</span> sums to <span class="math-container">$kT$</span>, set <span class="math-container">$b_1=\dots=b_k=T$</span> and <span class="math-container">$c_1,\dots,c_n$</span> the multiset.  Then there is a monochromatic assignment iff there is a valid solution to the multiway number partitioning problem.</p>

CC BY-SA 4.0
2023-03-22T07:13:15.933Z
Smart reduction :-)
AAArAAA
CC BY-SA 4.0
2023-03-22T06:26:18.170Z
2023-03-22T06:26:18.170Z
D.W.
<p>Suppose we have a collection of <span class="math-container">$m$</span> balls in <span class="math-container">$k$</span> different colors. Let <span class="math-container">$b_i$</span> be the number of balls with color <span class="math-container">$i$</span>, so <span class="math-container">$\sum_{i=1}^k b_i = m$</span>. Assume we have <span class="math-container">$n$</span> bins with capacities <span class="math-container">$c_1, \dots, c_n$</span>, such that <span class="math-container">$\sum_{j=1}^n c_j \geq m$</span>.</p>
<p>We say an assignment of balls into bins is <em>monochromatic</em> if it satisfies three conditions:</p>
<p>(I) Each ball is assigned to exactly one bin.</p>
<p>(II) Number of balls assigned to a bin is at most its capacity.</p>
<p>(III) A bin is either empty or monochromatic, i.e. it does NOT contain two balls with different colors.</p>
<p>Question: How do we decide for a given collection of <span class="math-container">$m$</span> balls with <span class="math-container">$k$</span> colors, and <span class="math-container">$n$</span> bins with capacities, whether there is a <em>monochromatic</em> assignment? Is this problem <span class="math-container">$NP$</span>-hard?</p>
<p>For example if we have two balls <span class="math-container">$b_1=7, b_2=3$</span>, then it is impossible to distribute them to two bins with capacities <span class="math-container">$c_1=5, c_2=6$</span>, but we can distribute them into three bins with capacities <span class="math-container">$c_1=5, c_2=2, c_3=3$</span>.</p>

<np-hardness><approximation-algorithms>
Balls in monochromatic bins
AAArAAA
# Balls in monochromatic bins

(Asked by: username_0 on 2023-03-22)

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

**Tags:** np-hardness, approximation-algorithms


---

## 1 answers

### Answer by username_1 on 2023-03-22. Score: 4 | Accepted answer

It is NP-hard, by reduction from [multiway number partitioning](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: Smart reduction :-)  

---

