TY - GEN
T1 - All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
AU - Assadi, Sepehr
AU - Bernstein, Aaron
AU - Langley, Zachary
N1 - Publisher Copyright:
© Sepehr Assadi, Aaron Bernstein, and Zachary Langley; licensed under Creative Commons License CC-BY 4.0.
PY - 2023/1/1
Y1 - 2023/1/1
N2 - In the weighted load balancing problem, the input is an n-vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real weight. The output is an assignment that maps each client to one of its adjacent servers, and the load of a server is then the sum of the weights of the clients assigned to it. The goal is to find an assignment that is well-balanced, typically captured by (approximately) minimizing either the ℓ∞- or ℓ2-norm of the server loads. Generalizing both of these objectives, the all-norm load balancing problem asks for an assignment that approximately minimizes all ℓp-norm objectives for p ≥ 1, including p = ∞, simultaneously. Our main result is a deterministic O(log n)-pass O(1)-approximation semi-streaming algorithm for the all-norm load balancing problem. Prior to our work, only an O(log n)-pass O(log n)-approximation algorithm for the ℓ∞-norm objective was known in the semi-streaming setting. Our algorithm uses a novel application of the multiplicative weights update method to a mixed covering/packing convex program for the all-norm load balancing problem involving an infinite number of constraints.
AB - In the weighted load balancing problem, the input is an n-vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real weight. The output is an assignment that maps each client to one of its adjacent servers, and the load of a server is then the sum of the weights of the clients assigned to it. The goal is to find an assignment that is well-balanced, typically captured by (approximately) minimizing either the ℓ∞- or ℓ2-norm of the server loads. Generalizing both of these objectives, the all-norm load balancing problem asks for an assignment that approximately minimizes all ℓp-norm objectives for p ≥ 1, including p = ∞, simultaneously. Our main result is a deterministic O(log n)-pass O(1)-approximation semi-streaming algorithm for the all-norm load balancing problem. Prior to our work, only an O(log n)-pass O(log n)-approximation algorithm for the ℓ∞-norm objective was known in the semi-streaming setting. Our algorithm uses a novel application of the multiplicative weights update method to a mixed covering/packing convex program for the all-norm load balancing problem involving an infinite number of constraints.
KW - Load Balancing
KW - Semi-Matching
KW - Semi-Streaming Algorithms
UR - http://www.scopus.com/inward/record.url?scp=85147545185&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85147545185&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2023.7
DO - 10.4230/LIPIcs.ITCS.2023.7
M3 - Conference contribution
AN - SCOPUS:85147545185
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
A2 - Kalai, Yael Tauman
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Y2 - 10 January 2023 through 13 January 2023
ER -