4 papers
Streaming and Communication Complexity of Load-Balancing via Matching Contractors
Sepehr Assadi, Aaron Bernstein, Zachary Langley +2
In the load-balancing problem, we have an -vertex bipartite graph between a set of clients and servers. The goal is to find an assignment of all clients to the ser…
Matching Composition and Efficient Weight Reduction in Dynamic Matching
Aaron Bernstein, Jiale Chen, Aditi Dudeja +3
We consider the foundational problem of maintaining a -approximate maximum weight matching (MWM) in an -node dynamic graph undergoing edge insertions and deleti…
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
Sepehr Assadi, Aaron Bernstein, Zachary Langley
In the weighted load balancing problem, the input is an -vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real w…
Improved Bounds for Distributed Load Balancing
Sepehr Assadi, Aaron Bernstein, Zachary Langley
In the load balancing problem, the input is an -vertex bipartite graph and a positive weight for each client . The algorithm must assign each client…