Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…
cs.DS2023
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…