Balls into bins via local search

cover time and maximum load

Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun

Research output: Contribution to conferencePaper

2 Citations (Scopus)

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.
Original languageEnglish
Pages187-198
Number of pages12
DOIs
Publication statusPublished - 1 Mar 2014
Event31st International Symposium on Theoretical Aspects of Computer Science - Lyon , France
Duration: 5 Mar 20148 Mar 2014

Conference

Conference31st International Symposium on Theoretical Aspects of Computer Science
CountryFrance
CityLyon
Period5/03/148/03/14

Fingerprint

Cover Time
Local Search
Ball
Upper bound
Graph in graph theory
Vertex-transitive
Vertex of a graph
Local Minima
Undirected Graph
Choose

Cite this

Bringmann, K., Sauerwald, T., Stauffer, A., & Sun, H. (2014). Balls into bins via local search: cover time and maximum load. 187-198. Paper presented at 31st International Symposium on Theoretical Aspects of Computer Science, Lyon , France. https://doi.org/10.4230/LIPIcs.STACS.2014.187

Balls into bins via local search : cover time and maximum load. / Bringmann, Karl; Sauerwald, Thomas; Stauffer, Alexandre; Sun, He.

2014. 187-198 Paper presented at 31st International Symposium on Theoretical Aspects of Computer Science, Lyon , France.

Research output: Contribution to conferencePaper

Bringmann, K, Sauerwald, T, Stauffer, A & Sun, H 2014, 'Balls into bins via local search: cover time and maximum load' Paper presented at 31st International Symposium on Theoretical Aspects of Computer Science, Lyon , France, 5/03/14 - 8/03/14, pp. 187-198. https://doi.org/10.4230/LIPIcs.STACS.2014.187
Bringmann K, Sauerwald T, Stauffer A, Sun H. Balls into bins via local search: cover time and maximum load. 2014. Paper presented at 31st International Symposium on Theoretical Aspects of Computer Science, Lyon , France. https://doi.org/10.4230/LIPIcs.STACS.2014.187
Bringmann, Karl ; Sauerwald, Thomas ; Stauffer, Alexandre ; Sun, He. / Balls into bins via local search : cover time and maximum load. Paper presented at 31st International Symposium on Theoretical Aspects of Computer Science, Lyon , France.12 p.
@conference{a4148efa0ad44c7cb351b06e280375a3,
title = "Balls into bins via local search: cover time and maximum load",
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.",
author = "Karl Bringmann and Thomas Sauerwald and Alexandre Stauffer and He Sun",
year = "2014",
month = "3",
day = "1",
doi = "10.4230/LIPIcs.STACS.2014.187",
language = "English",
pages = "187--198",
note = "31st International Symposium on Theoretical Aspects of Computer Science ; Conference date: 05-03-2014 Through 08-03-2014",

}

TY - CONF

T1 - Balls into bins via local search

T2 - cover time and maximum load

AU - Bringmann, Karl

AU - Sauerwald, Thomas

AU - Stauffer, Alexandre

AU - Sun, He

PY - 2014/3/1

Y1 - 2014/3/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84907853698&partnerID=8YFLogxK

UR - http://dx.doi.org/10.4230/LIPIcs.STACS.2014.187

UR - http://www.stacs-conf.org/

U2 - 10.4230/LIPIcs.STACS.2014.187

DO - 10.4230/LIPIcs.STACS.2014.187

M3 - Paper

SP - 187

EP - 198

ER -