Graphical balanced allocations and the (1 + β)‐choice process

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 , for large m. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to 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 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 “‐choice” process for some parameter : each ball goes to a random bin with probability and the lesser loaded of two random bins with probability β. For this process we show that the gap is , irrespective of m. Moreover the gap stays at 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