DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2023.7

All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method

Authors: Sepehr Assadi, Aaron Bernstein, and Zachary Langley

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

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 𝓁₂-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.

Cite as

Sepehr Assadi, Aaron Bernstein, and Zachary Langley. All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ITCS.2023.7,
  author =	{Assadi, Sepehr and Bernstein, Aaron and Langley, Zachary},
  title =	{{All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.7},
  URN =		{urn:nbn:de:0030-drops-175106},
  doi =		{10.4230/LIPIcs.ITCS.2023.7},
  annote =	{Keywords: Load Balancing, Semi-Streaming Algorithms, Semi-Matching}
}

Document

DOI: 10.4230/LIPIcs.DISC.2020.1

Improved Bounds for Distributed Load Balancing

Authors: Sepehr Assadi, Aaron Bernstein, and Zachary Langley

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract

In the load balancing problem, the input is an n-vertex bipartite graph G = (C ∪ S, E) - where the two sides of the bipartite graph are referred to as the clients and the servers - and a positive weight for each client c ∈ C. The algorithm must assign each client c ∈ C to an adjacent server s ∈ S. The load of a server is then the weighted sum of all the clients assigned to it. The goal is to compute an assignment that minimizes some function of the server loads, typically either the maximum server load (i.e., the 𝓁_∞-norm) or the 𝓁_p-norm of the server loads. 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 study load balancing in the distributed setting. There are two existing results in the CONGEST model. Czygrinow et al. [DISC 2012] showed a 2-approximation for unweighted clients with round-complexity O(Δ⁵), where Δ is the maximum degree of the input graph. Halldórsson et al. [SPAA 2015] showed an O(log n / log log n)-approximation for unweighted clients and O(log²n/log log n)-approximation for weighted clients with round-complexity polylog(n). In this paper, 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. Our approach also has implications for the standard sequential setting in which we obtain the first O(1)-approximation for this problem that runs in near-linear time. A 2-approximation is already known, but it requires solving a linear program and is hence much slower. Finally, we note that all of our results simultaneously approximate all 𝓁_p-norms, including the 𝓁_∞-norm.

Cite as

Sepehr Assadi, Aaron Bernstein, and Zachary Langley. Improved Bounds for Distributed Load Balancing. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.DISC.2020.1,
  author =	{Assadi, Sepehr and Bernstein, Aaron and Langley, Zachary},
  title =	{{Improved Bounds for Distributed Load Balancing}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{1:1--1:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.1},
  URN =		{urn:nbn:de:0030-drops-130798},
  doi =		{10.4230/LIPIcs.DISC.2020.1},
  annote =	{Keywords: Load Balancing, Distributed Algorithms, Matching, Semi-Matching}
}

Search Results

Documents authored by Langley, Zachary

All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method

Abstract

Cite as

Improved Bounds for Distributed Load Balancing

Abstract

Cite as

Thanks for your feedback!

Could not send message