CS Events Monthly View

Seminar

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 link: https://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