hide
Free keywords:
Mathematics, Probability, math.PR,Computer Science, Discrete Mathematics, cs.DM,Mathematics, Combinatorics, math.CO
Abstract:
We study a natural process for allocating m balls into n bins that are
organized as the vertices of an undirected graph G. Balls arrive one at a time.
When a ball arrives, it 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. Then the next
ball arrives and this procedure is repeated. For the case m = n, we give an
upper bound for the maximum load on graphs with bounded degrees. We also
propose the study of the cover time of this process, which is defined as the
smallest m so that every bin has at least one ball allocated to it. We
establish an upper bound for the cover time on graphs with bounded degrees. Our
bounds for the maximum load and the cover time are tight when the graph is
transitive or sufficiently homogeneous. We also give upper bounds for the
maximum load when m > n.
