1
$\begingroup$

I would like to ask you for a help about modified balls into bins problem. Consider $n$ weighted balls such that each ball has a weight $w_i$ that is at most $W$. Furthermore, each of $m$ bins has a maximum capacity $W$. We place $n$ balls into $m$ bins uniformly at random. That is, there are $m^n$ different assignments of balls to bins and all of them are equally likely.

If a ball $i$ with the weight $w_i$ lands into a random bin $j$ that already contains balls of total weight $w'_j$, then two cases are possible:

  1. $W \ge w'_j + w_i$: we put the ball into the bin and set $w'_j:= w'_j + w_i$
  2. $W < w'_j + w_i$ : we split the ball $i$ putting $W-w'_j$ of its weight to $j$-th bin and proceed to insert the $i$-th ball with the new weight $w_i:=w_i-W+w'_j$ to the bin $j + 1 \mod{m}$.

If this helps its a modified linear probing algorithm, when we insert super keys into a hash table, where each super key consists of at most $W$ keys.

Now assume that we already have $n$ balls with weights $w_1, \dots, w_x$ in $m$ bins. The total weight of the balls is $\mathcal{W}$ and $\mathcal{W}$ is a multiple of $W$. Let $E[T]$ is the average number of bins visited during the insertion of a new ball with the weight $W$. I want to show that $E[T]$ is maximized when we insert $x = \mathcal{W}/W$ balls with the weight $W$ each.

Example: we have $\mathcal{W} = 8$, $W = 2$ and $m=16$. We can insert $x=5$ balls: $\{1, 1, 2, 2, 2\}$ or $x=4$ balls: $\{2, 2, 2, 2\}$ and so on. The only condition is that the total weight of the balls is $8$ and the maximum weight of each ball is $2$. I want to show that $E[T]$ is maximized when we insert $x=4$ balls with maximum weight $2$.

Could you please advise me some approaches or papers to tackle this problem. Thank you very much.

$\endgroup$
  • $\begingroup$ Fixed it. Will copy it here as well. We place $n$ balls into $m$ bins uniformly at random. That is, there are $m^n$ different assignments of balls to bins and all of them are equally likely. $\endgroup$ – rbtrht Dec 21 '19 at 21:22
  • 1
    $\begingroup$ So you fix $n$ balls with weights $w_1, \ldots, w_n$, then perform the following random experiment: insert each of the $n$ balls randomly as described in the post, then insert one more ball of weight $W$, and let r.v.$~T$ be the number of bins visited during the insertion of that last ball. You want to show that, for any integer $k\ge 0$, over all choices of $n$ and $w_1,\ldots, w_n$ such that $\sum_i w_i = kW$ (and $0\le w_i\le W$ for all $i$), the choice $n=k$ and $W, W, \ldots, W$ ($k$ times) maximizes $E[T]$? $\endgroup$ – Neal Young Dec 21 '19 at 23:10
  • $\begingroup$ Yes, you are correct! $\endgroup$ – rbtrht Dec 22 '19 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.