  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 that this process
yields a maximum load of only \Theta(\log \log n) on expander graphs. In
addition, we show that for d-dimensional grids the maximum load is
\Theta\Big(\big(\frac{\log n}{\log \log n}\big)^{\frac{1}{d+1}}\Big). Finally,
for almost regular graphs with minimum degree \Omega(\log n), we prove that the
maximum load is constant and also reveal a fundamental difference between
random and arbitrary tie-breaking rules.
