CS Events

PhD Defense All-Norm Load Balancing in Massive Graphs
Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Thursday, March 21, 2024, 10:00am - 12:00am

Speaker: Zachary Langley

Location : CoRE 305

Committee: 

Aaron Bernstein (advisor)

Sepehr Assadi

Jie Gao

Christian Konrad (external)

Event Type: PhD Defense

Abstract: We address the all-norm load balancing problem in bipartite graphs in the distributed and semi-streaming models. In the all-norm load balancing problem, we are given a bipartite graph with weights on the clients. The goal is to assign each client to an adjacent server such that the Lp norm of the server load vector is approximately minimized for all p simultaneously. We present the first O(1)-approximation algorithm in the CONGEST model that runs in polylog(n) rounds. In the semi-streaming model, we develop an O(1)-approximation O(log n)-pass algorithm using different techniques. Additionally, these algorithms are can be ported to the sequential model, yielding the first O(1)-approximation for the problem that runs in near-linear time.

: 

Contact  Assistant Professor Aaron Bernstein (advisor)