ARC Colloquium: Nikhil Bansal (Univ. of Michigan)

Algorithms & Randomness Center (ARC)

Nikhil Bansal (Univ. of Michigan)

Monday, February 21, 2022

Klaus 1116 East - 11:00 am


Title:  More on the power of two choices in balls and bins

Abstract:  I will describe some recent results on generalizations of the classical two choices model for balls into bins processes.

One such generalization 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 extension is where the balls can also be deleted arbitrarily by an oblivious adversary. Interestingly, in both cases the natural greedy strategy can be far from optimal, and I will describe other strategies for these settings that are close to optimal.

Based on joint works with Ohad Feldheim and William Kuszmaul.


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Event Details


  • Monday, February 21, 2022
    11:00 am - 12:00 pm