Balanced Allocation Through Random Walk

Alan Frieze, Samantha Petti

We consider the allocation problem in which $m\le (1-\epsilon )dn$ items are to be allocated to $n$ bins with capacity $d$. The items $x_1,x_2,\dots ,x_m$ arrive sequentially and when…