Uniformly distribute N colored balls to P players, minimizing number of colors

Question

I am facing the following combination problem :

I do have $B$ colored boxes, each one containing $N_b$ balls of the given color. The total number of balls is thus $\sum_{b=1}^{B} N_b = N$.

I want to distribute the balls to P players with the two following aims:

• The number of balls received by each player must be the same (ie $N/P$)
• The sum of the number of different colors hold by each player must be minimal : if each player get $c_p$ different colors, I want $\sum_{p=1}^{P} c_p$ as small as possible.

Is there any formulae or algorithm to respect both constraints ?

Edit

What is this problem useful ?

This problem arises eg in scientific computing : you have a available number of processus ($P$) and you want to perform arithmetics on several ($B$) arrays of different sizes ($N_b$). Obviously you want the arrays to be uniformly distributed (otherwise one process will have much more work and will slow the whole procedure), but you also want to minimize the splits in the original arrays since each one implies a communication between processus, which are also time consuming.

What to start with :

I guess we can easily fall back to the case of a distribution $\tilde D=\{\tilde N_1, \tilde N_2, ... \tilde N_{B}\}$ to distribute on P' players, with $P' \le P$ and $\tilde N_b < N/P$ : indeed, any boxe in the original distribution having more than $N/P$ ball will fill up 100% capacity of one (or more) player. We can then try to do pairs (or triplets, etc.) with the remaining boxes to reach N/P, but we may not have a perfect match without cuts in the general case.

Answer 1

Well, it is easy to divide the balls such that $\displaystyle\sum_{p=1}^{P} c_p=B+P-1$. You first give out as many balls as you can from box $1$ to player $1$. Then if the box becomes empty, you give away from the next box. If some player receives $\frac{N}{P}$ balls, you move on to the next player.

In general cases, that's the best you can do. In the next section, I tweak this strategy slightly to get the optimal distribution.

The following is a recursive algorithm to find the distribution for given $D=\{N_1,N_2,...,N_B\}$:

1. Find the minimum $k$ such that there exists subset $S$ of $D$ with sum $k\cdot\frac{N}{P}$.
2. Give away the balls corresponding to $S$ to $k$ players.
3. Repeat with $D$ replaced by $D-S$.

If this algorithm runs $t$ times, it is easy to see that $\displaystyle\sum_{p=1}^{P} c_p=B+P-t$. This is indeed the best possible.

Answer 2

You can solve the problem via integer linear programming as follows. Let nonnegative integer decision variable $x_{b,p}$ be the number of balls of color $b$ distributed to player $p$. Let binary decision variable $y_{b,p}$ indicate whether $x_{b,p}>0$. The problem is to minimize $\sum_{b,p} y_{b,p}$ subject to: \begin{align} \sum_p x_{b,p} &=N_b &&\text{for all $b$}\\ \sum_b x_{b,p} &=N/P &&\text{for all $p$}\\ x_{b,p} &\le M_{b,p} y_{b,p} &&\text{for all $b$ and $p$} \end{align} Here $M_{b,p}$ is a "big-M" constant upper bound on $x_{b,p}$. A good choice is $M_{b,p}=\min(N_b,N/P)$.