Seminar Details
Improved Bounds for Distributed Load Balancing
- Start Date: September 23, 2020
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Organizers: Sepehr Assadi || Swastik Kopparty
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Zach Langley - Rutgers University
- Event Location: Online Event
- Event Additional Info: <p>The <strong>Theory of Computing Seminar is being held online. </strong>Contact the organizers for the link to the seminar.</p>
- Presentation Type: Stand Alone Presentation
- 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.