Balls into bins via local search: cover time and maximum load
OPEN ACCESS
Loading...
Author / Producer
Date
2014
Publication Type
Conference Paper
ETH Bibliography
no
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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 vertex transitive or sufficiently homogeneous. We also give upper bounds for the maximum load when m>=n.
Permanent link
Publication status
published
External links
Book title
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Volume
25
Pages / Article No.
187 - 198
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Balls and Bins; Stochastic Process; Randomized Algorithm; Balls and Bins; Stochastic Process
Organisational unit
03672 - Steger, Angelika / Steger, Angelika