CS Events


Improved Bounds for Distributed Load Balancing


Download as iCal file

Wednesday, September 23, 2020, 11:00am - 12:00pm


Rutgers/DIMACS Theory of Computer Seminar


Zoom linkhttps://rutgers.zoom.us/j/92684396735?pwd=TmZNZVUvdmxtMGxUeWVKVndWazB5dz09
Meeting ID: 926 8439 6735


Speaker: Zach Langley (Rutgers University)

Location : via Zoom

Event Type: Seminar

Abstract: We consider the problem of load balancing in the distributed setting. The input is a bipartite graph on clients and servers, where each client comes with a positive weight. The algorithm must assign each client to an adjacent server, 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 show the first distributed algorithms 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 for unweighted clients. For weighted clients, the approximation ratio is O(log(n)). In the less constrained LOCAL model, we give an O(1)-approximation algorithm for weighted clients in polylog(n) rounds. Based on joint work with Sepehr Assadi and Aaron Bernstein.

Contact  Professor Sepehr Assadi