(Almost) Perfect Discrete Iterative Load Balancing
summary
Shows that for a fully random insert/delete balls-into-bins process, if insertion probabilities stay bounded away from 0 the number of balls above average is linear and the discrepancy is O(log n), and this is tight (e.g. a 1/2−ε insertion bias can push max load to log n). Starting from a perfectly balanced state the process stays at log log n + O(1) discrepancy for polynomial (≈n^5) time. Proof uses Peres–Talwar–Wieder potentials, layered induction, recovery arguments and Markov-chain couplings; Greedy-2 performs well under random updates.
AI-written summary · about
chapters (6)
- 0:00Infinite balls into bins
- 2:50Balls into bins models
- 4:18Randomized model and results
- 9:28Proof techniques and analysis
- 13:58Recovery properties and induction
- 16:57Conclusion and questions
related talks
27mAll-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
40mResilience of 3-Majority Dynamics to Non-Uniform Schedulers
20mBeyond Worst-Case Budget-Feasible Mechanism Design
01h 10mComplexity and Algorithmic Game Theory II
34mTesting Intersectingness of Uniform Families or how Dana and I intersected
01h 02mFine-Grained Counting Complexity I
26mLower Bounds on the Running Time for Scheduling and Packing Problems
01h 01mComplexity and Algorithmic Game Theory I