Balls into bins via local search: Cover time and maximum load |
| |
| Authors: | Karl Bringmann Thomas Sauerwald Alexandre Stauffer He Sun |
| |
| Affiliation: | 1. Institute for Theoretical Computer Science, ETH Zurich, Switzerland;2. Computer Laboratory, University of Cambridge, UK;3. Department of Mathematical Sciences, University of Bath, UK;4. Department of Computer Science, University of Bristol, UK |
| |
| Abstract: | Abstract–We study a natural process for allocating  balls into  bins that are organized as the vertices of an undirected graph  . Balls arrive one at a time. When a ball arrives, it first chooses a vertex  in  uniformly at random. Then the ball performs a local search in  starting from  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  , 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  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  . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 681–702, 2016 |
| |
| Keywords: | balls‐into‐bins load balancing stochastic process local search |
|
|
