Well-Balanced Allocation on General Graphs

We study the graphical generalization of the 2-choice balls-into-bins process, where rather than choosing any two random bins, the bins correspond to vertices of an underlying graph, and only the bins connected by an edge can be chosen. For any $k(n)$ edge-connected, $d(n)$-regular graph on $n$ vertices and any number of balls, we give an allocation strategy which guarantees that the maximum gap between the bin loads is $O((d/k) \log^4n \log \log n)$, with high probability. We further show that the dependence on $k$ is tight and give an $\Omega((d/k) + \log n)$ lower bound on the gap achievable by any allocation strategy, for any graph $G$. In particular, our result gives polylogarithmic bounds for natural graphs such as cycles and tori, where the classical greedy allocation appears to result in a polynomial gap. Previously such a bound was known only for graphs with good expansion. The construction is based on defining certain orthogonal flows on cut-based R\"{a}cke decomposition of graphs. The allocation algorithm itself, however, is simple to implement and takes only $O(\log(n))$ time per allocation, and can be viewed as a global version of the greedy strategy that compares average load on sets of vertices, rather than on individual vertices.