CS Events Monthly View

By Year

By Month

By Week

Today

Jump to month

January February March April May June July August September October November December 2021 2022 2023 2024 2025 2026 2027 2028 Jump to month

Qualifying Exam Improved Bounds for Distributed Load Balancing
× 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 Monday, May 09, 2022, 04:00pm

:

Location : Via Zoom

Committee: 

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.

Organization: 

Rutgers University School of Arts and Sciences

Contact  Sepehr Assadi