Graphical balanced allocations and the (1 + β)‐choice process. Issue 4 (22nd July 2014) - Peres, Yuval; Talwar, Kunal; Wieder, Udi
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgqzz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(mlognn)</alternatives>, for large m. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgr3h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(loglogn)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgr20" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O(logn/σ)</alternatives> 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 "<alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgr1g" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(1+β)</alternatives>‐choice" process for some parameter <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgr0z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />β∈(0, 1)</alternatives>: each ball goes to a random bin with probability <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgqwx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(1−β)</alternatives> and the lesser loaded of two random bins with probability β. For this process we show that the gap is <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgqvd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(logn/β)</alternatives>, irrespective of m. Moreover the gap stays at <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgqsc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(logn/β)</alternatives> 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