In the load-balancing problem, we have an n-vertex bipartite graph G = (L, R, E ) between a set of clients and servers. The goal is to find an assignment of all clients to the servers, while minimizing the maximum load on each server, where load of a server is the number of clients assigned to it. Motivated by understanding the streaming complexity of this problem, we study load-balancing in the one-way (two-party) communication model: the edges of the input graph are partitioned between Alice and Bob, and Alice needs to send a short message to Bob for him to output a solution of the entire graph.

We consider the foundational problem of maintaining a (1 — ε )-approximate maximum weight matching (MWM) in an n-node dynamic graph undergoing edge insertions and deletions. We provide a general reduction that reduces the problem on graphs with a weight range of poly(n ) to poly(1/ε ) at the cost of just an additive poly(1/ε ) in update time. This improves upon the prior reduction of Gupta-Peng (FOCS 2013) which reduces the problem to a weight range of ε-O (1/ε) with a multiplicative cost of O (log n ).

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 $\ell_\infty$- or $\ell_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 $\ell_p$-norm objectives for $p \ge 1$, including $p = \infty$, 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 $\ell_\infty$-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.

We introduce a new framework for computing approximate maximum weight matchings. Our primary focus is on the fully dynamic setting, where there is a large gap between the guarantees of the best known algorithms for computing weighted and unweighted matchings. Indeed, almost all current weighted matching algorithms that reduce to the unweighted problem lose a factor of two in the approximation ratio. In contrast, in other sublinear models such as the distributed and streaming models, recent work has largely closed this weighted/unweighted gap.

In the load balancing problem, the input is an $n$-vertex bipartite graph $G = (C \cup S, E)$ and a positive weight for each client $c \in C$. The algorithm must assign each client $c \in C$ to an adjacent server $s \in S$. The load of a server is then the weighted sum of all the clients assigned to it, and the goal is to compute an assignment that minimizes some function of the server loads, typically either the maximum server load (i.e., the $\ell_{\infty}$-norm) or the $\ell_p$-norm of the server loads. 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(Δ^5)$, 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^2\!{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 $\ell_p$-norms, including the $\ell_{\infty}$-norm.