Balls into bins via local search
Paul Bogdan, Thomas Sauerwald, Alexandre O. Stauffer, He Sun · 2013
We propose a natural process for allocating n balls into n bins that are organized as the vertices of an undirected graph G. Each ball first chooses a vertex u in G uniformly at random. Then the ball performs a local search in G starting from u until it reaches a vertex with local minimum load, where the ball is finally placed on. In our main result, we prove thatthisprocessyieldsamaximumloadofonlyΘ(loglogn)onexpandergraphs. Inaddition, ( ( logn we show that for d-dimensional grids the maximum load is Θ loglogn) 1 d+1. Finally, for almost regular graphs with minimum degree Ω(logn), we prove that the maximum load is constantandalsorevealafundamentaldifferencebetweenrandomandarbitrarytie-breaking rules. 1