Balanced Allocations with Heterogeneous Bins: The Power of Memory

Dimitrios Los, Thomas Sauerwald, John Sylvester

We consider the allocation of $m$ balls (jobs) into $n$ bins (servers). In the standard Two-Choice process, at each step $t=1,2,\dots ,m$ we first sample two bins uniformly at rand…