# 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

**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.

**Bio:**

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.