# Balanced Allocations with Heterogeneous BinsThe Power of Memory

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.

## One-Choice

The $\OneChoice$ process is the simplest randomised allocation process. Each ball is allocated to a bin sampled uniformly at random.

Your browser does not support the HTML5 canvas tag.

## Two-Choice

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.

Your browser does not support the HTML5 canvas tag.

## Memory

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.

Your browser does not support the HTML5 canvas tag.

## Power of Memory

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

Your browser does not support the HTML5 canvas tag.

Memory

Your browser does not support the HTML5 canvas tag.