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.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
