Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
summary
Handles fully dynamic online d‑dimensional scheduling with m machines and proves a randomized algorithm against an oblivious adversary achieves competitive ratio Theta(log d / log log d) while keeping constant recourse per job. Construction duplicates machines into a Random set and a Greedy set, sets per‑job prefix property thresholds based on average and max loads (AL_k, ML), only rebalances when thresholds halve, and uses Chernoff bounds plus Westbrook ’94 one‑dimensional balancing. Shows probability a job moves to Greedy ≤ 1/d and leaves open adaptive‑adversary and recourse‑dependent lower bounds.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:15The Problem
- 1:01Example - Greedily Minimize Makespan
- 1:55Better Assignment Exists
- 2:14Deletion Issues
- 4:16Lower Bounds on Optimal Makespan
- 5:14Naive Attempt 1: Inserting Greedily
- 5:33Naive Attempt 1: Flattened Greedy
- 6:18Naive Attempt 2: Inserting Randomly
- 6:56Attempt 3: Combine Both
- 7:52Attempt 3: Random + Greedy
- 8:54Analysis Sketch of Random + Greedy
- 9:34Deletion Hurdles
- 10:39Insertion of Job j
- 12:19Stabilization Procedure
- 13:05Deletion of Job j - Stabilization
- 14:11Bounds on Recourse
- 14:41Sending Jobs to Greedy
- 15:19Bounds on Competitive Ratio
- 16:50Competitive Ratio - Random Set
- 17:22Competitive Ratio - Greedy Set
- 17:43Conclusion
related talks
19mDistributed load balancing: a new framework and improved guarantees
26mEfficient load balancing in distributed systems
25mAvoiding Overload in Distributed Systems
17mApplication of Online Resource Allocation Based on Ray
19mDynaRL: Flexible and Dynamic Scheduling of Large-Scale Reinforcement Learning Training
21mEffective Straggler Mitigation: Attack of the Clones
35mApproximation hardness and online algorithms for resource scheduling
39mSketching and Randomization for Distributed Submodular and Coverage Optimization