2026-09-10T09:44:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27771 2026-09-09T12:19:38Z ddc:004 open_access

Load Balancing Under Adaptive Bin Deletions Kaplan, Haim Sapir, Shay Stemmer, Uri Balls and Bins Adaptive Adversary 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((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 ≪ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haim Kaplan and Shay Sapir and Uri Stemmer 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.54 urn:nbn:de:0030-drops-277711 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.54 eng https://creativecommons.org/licenses/by/4.0/legalcode