On this page, you will find a few visualisations for the processes mentioned in the "Balanced Allocations with Heterogeneous Bins: The Power of Memory" by D. Los, T. Sauerwald and J. Sylvester, presented at SODA 2023. The general visualiser may also be of interest.
The $\OneChoice$ process is the simplest randomised allocation process. Each ball is allocated to a bin sampled uniformly at random.
An improvement over $\OneChoice$ is the $\TwoChoice$ process, where for each ball two bins are sampled uniformly. The ball is then allocated in the least loaded of the two bins.
The $\Memory$ process has the ability to store a bin in a cache. For each ball, it takes a random sample and allocates to the least loaded of the cache and the bin.
In the setting with heterogeneous sampling distributions, for sufficiently large constant imbalance, the $\TwoChoice$ process may have a gap that diverges in $m$ w.h.p., while $\Memory$ still atains the $\Oh(\log \log n)$ gap.
Two-Choice
Memory
.
.