CS Events

Qualifying Exam

Improved Bounds for Distributed Load Balancing


Download as iCal file

Monday, May 09, 2022, 04:00pm



Location : Via Zoom


Sepehr Assadi (Advisor)

Aaron Bernstein

Martin Farach-Colton

Vladimir Pavlovic

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