The power of two choices for balls into bins: Beyond greedy strategies

Date: March 2, 2023
Time: 4:00 pm
Room: DBH 4011
Speaker: Nikhil Bansal 
(University of Michigan)

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.

Nikhil Bansal is the Patrick C. Fischer professor in the Computer Science department

at the University of Michigan. He obtained his PhD from Carnegie Mellon University,
and has previously worked at IBM T.J. Watson Labs, and TU Eindhoven and CWI in the Netherlands.
He is broadly interested in theoretical computer science with focus on algorithm design,
discrete mathematics and optimization. He is a recipient of an ERC Consolidator award,
NWO VIDI and VICI awards, and was an invited speaker at the 2022 International Congress of Mathematicians.

Close Menu
Skip to content