The power of two choices: Beyond greedy strategies
Thursday, October 26, 2023, 11 AM
Bahen Centre for Information Technology, BA 3200
This lecture is open to the public.
No registration is required but space is limited.
Abstract:
The power of two choices for placing balls into bins is a highly influential paradigm with applications in areas such as networking, distributed computing and hashing. Here, when a ball arrives we select two random bins and place the ball greedily in the least loaded of the two bins. It is well-known that this leads to substantially better load balancing than a random assignment.
Perhaps surprisingly, this greedy strategy can be quite sub-optimal in some natural settings, e.g., when balls can also be deleted, or there are constraints on which two bins can be queried. In this talk, I will describe why the greedy strategy can perform poorly, and present new strategies that are close to optimal. The talk will be a gentle introduction to the topic of balls and bins and does not require any prior background.
Bio:
Nikhil Bansal is the Patrick C. Fischer professor of Computer Science and Engineering at the University of Michigan, Ann Arbor. He completed his PhD from Carnegie Mellon University, and has previously worked at IBM Research, TU Eindhoven and CWI Amsterdam. He is broadly interested in theoretical computer science with focus on the design and analysis of algorithms, discrete mathematics and combinatorial optimization.