Improved Bounds for Distributed Load Balancing
Monday, May 09, 2022, 04:00pm
Location : Via Zoom
Sepehr Assadi (Advisor)
Event Type: Qualifying Exam
Abstract: We consider the problem of load balancing in the distributed setting. The input is a bipartite graph of clients and servers where each client comes with a positive weight. The goal is to assign each client to one of its adjacent servers minimizing the weighted sum of clients assigned to any one server. This problem has a variety of applications and has been widely studied under several different names, including scheduling with restricted assignment, semi-matching, and distributed backup placement. We give the first LOCAL algorithm to compute an O(1)-approximation to the load balancing problem in polylog(n) rounds. In the CONGEST model, we give an O(1)-approximation algorithm in polylog(n) rounds when the client weights are uniform; for general weights, the approximation ratio is O(log(n)). Based on joint work with Sepehr Assadi and Aaron Bernstein.
Rutgers University School of Arts and Sciences
Contact Sepehr Assadi