Balanced Allocation Through Random Walk

Abstract

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 item $x_i$ arrives it is given two possible bin locations $p_i=h_1(x_i),q_i=h_2(x_i)$ via hash functions $h_1,h_2$. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided $\epsilon =\Omega \left(\sqrt{\frac{\log d}{d}}\right).$

7 pages