Theory Seminar: Balanced Allocations: Simplifications and Generalizations

Udi Wieder (Microsoft Research)

Wednesday, 24.06.2009, 15:00

Room 337-8 Taub Bld.

Say we place m balls sequentially into n bins, where each ball is placed by
randomly selecting d bins and placing it in the least loaded of them. What is
the load of the maximum bin when m>>n? It is well known that when d=1 the
maximum load is m/n + \tildeO(sqrt(m/n)), whereas when d>=2 the maximum load is
m/n + loglog n. Thus when more than one bin is sampled, the gap between maximum
and average does not increase with the number of balls. We investigate a larger
family of placement schemes. We focus on the case where each time a ball is
placed, with probability half we use d=1 and with probability half we use d=2.
We show that the maximum load for this process is m/n + log n. Thus,
surprisingly, even though half the balls are thrown using a one-choice scheme,
the gap between maximum load and average load does not increase with the number
of balls. Along the way we develop new proof techniques which greatly simplify
existing proofs and show general conditions under which a placement scheme
outputs a balanced allocation.

Joint work with Kunal Talwar and Yuval Peres

Joint work with Kunal Talwar and Yuval Peres