All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
summary
Algorithm gives a semi-streaming (O~(n) space) method that uses the multiplicative weights update method to reduce all-norm load balancing to an oracle solved in one pass, then rounds a fractional solution to an integral assignment. It provably outputs a constant approximation for all Lp norms (handles weighted clients) using log n passes overall; matching hierarchies and greedy merges achieve the oracle with constant width, improving past sqrt(n) and log n approximations.
AI-written summary · about
chapters (11)
- 0:00The Load Balancing Problem
- 2:52(Multi-Pass) Graph Streaming Model
- 3:27Load Balancing in the Semi-Streaming Model
- 4:42B-All-Norm Load Balancing Convex Program
- 6:32B-All-Norm Oracle Problem (for MWU)
- 10:34Charging Scheme for Assignments
- 12:13Matching Hierarchy Decomposition
- 15:59Criteria for Good All-Norm Assignment
- 19:16Properties of the Partial Assignment
- 22:49Algorithm for Unweighted Clients
- 26:20Conclusion
related talks
20m(Almost) Perfect Discrete Iterative Load Balancing
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
01h 23mLoad balance and cache affinity: Friends, foes, or frenemies?
33mManaging High-Bandwidth Memory is a Parallel Scheduling Problem
34mNew Tools for Peak Memory Scheduling
32mCompetitive Data Structure Dynamization
31mPrivacy-preserving decentralized memory for federated learning (aka secure MPC)
01h 04mThe challenge of managing parallelism and data-movement for tensor computations on GPUs