Departmental Colloquium
Nikhil Bansal
University of Michigan
The power of two choices for balls into bins: Beyond greedy strategies
Abstract: In the classical two-choice process for assigning balls into bins, each ball chooses
two bins uniformly at random and is placed greedily in the least loaded of the two
bins. This power-of-two-choices paradigm has been highly influential and leads
to substantially better load balancing than a random assignment of balls into bins.
Somewhat surprisingly, the greedy strategy turns out to be quite sub-optimal
for some natural generalizations. One such setting is the graphical process
where the bins correspond to the vertices of a graph G, and at any time
a random edge is picked and a ball must be assigned to one of its end-points.
Another setting is where the balls can also be deleted arbitrarily by an oblivious
adversary. In this talk we will see why the greedy strategy can perform poorly, and
I will describe other strategies for these settings that are close to optimal.
Based on joint works with Ohad Feldheim and William Kuszmaul.
Friday October 28, 2022 at 3:00 PM in 636 SEO