  In dynamic load balancing, we wish to distribute balls into bins in an
environment where both balls and bins can be added and removed. We want to
minimize the maximum load of any bin but we also want to minimize the number of
balls and bins affected when adding or removing a ball or a bin. We want a
hashing-style solution where we given the ID of a ball can find its bin
efficiently.
  We are given a balancing parameter $c=1+\epsilon$, where $\epsilon\in (0,1)$.
With $n$ and $m$ the current numbers of balls and bins, we want no bin with
load above $C=\lceil c n/m\rceil$, referred to as the capacity of the bins.
  We present a scheme where we can locate a ball checking $1+O(\log
1/\epsilon)$ bins in expectation. When inserting or deleting a ball, we expect
to move $O(1/\epsilon)$ balls, and when inserting or deleting a bin, we expect
to move $O(C/\epsilon)$ balls. Previous bounds were off by a factor
$1/\epsilon$.
  These bounds are best possible when $C=O(1)$ but for larger $C$, we can do
much better: Let $f=\epsilon C$ if $C\leq \log 1/\epsilon$,
$f=\epsilon\sqrt{C}\cdot \sqrt{\log(1/(\epsilon\sqrt{C}))}$ if $\log
1/\epsilon\leq C<\tfrac{1}{2\epsilon^2}$, and $C=1$ if $C\geq
\tfrac{1}{2\epsilon^2}$. We show that we expect to move $O(1/f)$ balls when
inserting or deleting a ball, and $O(C/f)$ balls when inserting or deleting a
bin.
  For the bounds with larger $C$, we first have to resolve a much simpler
probabilistic problem. Place $n$ balls in $m$ bins of capacity $C$, one ball at
the time. Each ball picks a uniformly random non-full bin. We show that in
expectation and with high probability, the fraction of non-full bins is
$\Theta(f)$. Then the expected number of bins that a new ball would have to
visit to find one that is not full is $\Theta(1/f)$. As it turns out, we obtain
the same complexity in our more complicated scheme where both balls and bins
can be added and removed.
