Graphical balanced allocations and the (1 + β)‐choice process. Issue 4 (22nd July 2014) - Peres, Yuval
Abstract Suppose m balls are sequentially thrown into n bins where each ball goes into a random bin. It is well‐known that the gap between the load of the most loaded bin and the average is Θ(mlognn), for large m. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to Θ(loglogn) independent of m. Consider a constrained setting where not all pairs of bins can be sampled. We are given a graph where each node corresponds to a bin. The process sequentially samples an edge from the graph and places a ball in the lesser loaded of its endpoints. We show the gap is at most O(logn/σ) where σ is the edge expansion of the graph. Our results extend naturally to the hypergraph version of this question. Our technique involves a tight analysis of what we call the "(1+β)‐choice" process for some parameter β∈(0, 1): each ball goes to a random bin with probability (1−β) and the lesser loaded of two random bins with probability β. For this process we show that the gap is Θ(logn/β), irrespective of m. Moreover the gap stays at Θ(logn/β) in the weighted case for a large class of weight distributions. No non‐trivial bounds were previously known in the weighted case, even for the 2‐choice case. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 760–775, 2015