1
$\begingroup$

$S$ people, $N$ bins, each person has a given subset of bins he can cover, each person is given $t$ balls.

Question: What is the maximum value of the minimum number of balls per bin? i.e., allocate balls to maximize the minimum number of balls per bin, then compute the optimal minimum number.

1 Answers 1

1

There are $St$ total balls, so unless coverage is a problem you can have at least $\lfloor\frac{St}{N}\rfloor$ balls in each bin. The coverage becomes a problem if you can't spread the balls that evenly. For example, if there are three bins and two people. If person 1 can cover bins 1 and 2 and person 3 can cover bin 3, the minimum can ignore person 2 and bin 3. With more people and bins it can be more complicated, but without information on that we can't say more.