Load Balancing under Adaptive Bin Deletions

Haim Kaplan, Shay Sapir, Uri Stemmer

We analyze a balls-and-bins game against an adaptive adversary that sequentially deletes bins. Starting with $n$ balls distributed across $n$ bins, the adversary deletes a bin in e…