{"ID":6023549,"CreatedAt":"2026-07-08T01:00:23.257252134Z","UpdatedAt":"2026-07-10T12:31:16.415490432Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06211","arxiv_id":"2607.06211","title":"Load Balancing under Adaptive Bin Deletions","abstract":"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 each step, forcing the algorithm to redistribute its balls to surviving bins. We prove that after $n/2$ rounds, uniform random redistribution yields optimal $O(n)$ recourse and $O(\\frac{\\log n}{\\log \\log n})$ maximum load. Furthermore, we show that applying the ``power of two choices'' reduces the maximum load to $O(\\log \\log n)$ while maintaining linear recourse. We also consider a variation of this game where the balls from the deleted bin are partitioned evenly among $d \\ll n$ random bins rather than being redistributed independently. We demonstrate that keeping the balls together ($d=1$), which gives small maximum load and recourse against an oblivious adversary, fails against an adaptive adversary. Nevertheless, we show that splitting the balls into just two groups ($d=2$) is sufficient to recover linear recourse and efficient load balancing in the adaptive setting.","short_abstract":"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 each step, forcing the algorithm to redistribute its balls to surviving bins. We prove that after $n/2$ rounds, uniform random redistribution...","url_abs":"https://arxiv.org/abs/2607.06211","url_pdf":"https://arxiv.org/pdf/2607.06211v1","authors":"[\"Haim Kaplan\",\"Shay Sapir\",\"Uri Stemmer\"]","published":"2026-07-07T12:34:50Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}