The power of two choices for placing balls into bins is a highly influential paradigm with widespread use in both theory and practice. 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.
