Organizer(s):

Sepehr Assadi, Rutgers University

Swastik Kopparty, Rutgers University

Zach Langley, Rutgers University

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.

The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.