Streaming and Communication Complexity of Load-Balancing via Matching Contractors

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 show that settling the one-way communication complexity of load-balancing is equivalent to a natural sparsification problem for load-balancing, which can alternatively be interpreted as sparsification for vertex-expansion. We then prove a dual interpretation of this sparsifier, showing that the minimum density of a sparsifier is effectively the same as the maximum density one can achieve for an extremal graph family that is new to this paper, called Matching-Contractors; these graphs are intimately connected to the well-known Ruzsa-Szemerédi graphs and generalize them in certain aspects. Our chain of equivalences thus shows that the one-way communication complexity of load-balancing can be reduced to a purely graph theoretic question: what is the maximum density of a Matching-Contractor on n vertices? As our final result, we present a novel combinatorial construction of some-what dense Matching-Contractors, which implies a strong one-way communication lower bound for load-balancing: any one-way protocol (even randomized) with O^e(n) communication cannot achieve a better than n^{41 −}o⁽¹⁾approximation. Previously, no non-trivial lower bounds were known for protocols with even O(n log n) bits of communication (a better-than 2-approximation lower bound is trivial). Our result also implies the first non-trivial lower bounds for semi-streaming load-balancing in the edge-arrival model, ruling out n^{14 −}o⁽¹⁾-approximation in a single-pass.