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.