Balls into Bins via Local Search

Paul Bogdan; Thomas Sauerwald; Alexandre Stauffer; He Sun

doi:10.1137/1.9781611973105.2

Balls into Bins via Local Search

Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, He Sun

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 Θ(log log n) on expander graphs. In addition, we show that for d-dimensional grids the maximum load is Θ(((log n)/(log log n))(1/(d+1))). Finally, for almost regular graphs with minimum degree Ω(log n), we prove that the maximum load is constant and also reveal a fundamental difference between random and arbitrary tie-breaking rules.

Original language	English
Title of host publication	Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013
Pages	16-34
Number of pages	19
ISBN (Electronic)	978-1-61197-310-5
DOIs	https://doi.org/10.1137/1.9781611973105.2
Publication status	Published - 2013
Event	Twenty-Fourth Annual ASM-SIAM Symposium on Discrete Algorithms - Astor Crowne Plaza Hotel, New Orleans, United States Duration: 6 Jan 2013 → 8 Jan 2013 http://www.siam.org/meetings/da13/index.php

Conference

Conference	Twenty-Fourth Annual ASM-SIAM Symposium on Discrete Algorithms
Abbreviated title	SODA 2013
Country/Territory	United States
City	New Orleans
Period	6/01/13 → 8/01/13
Internet address	http://www.siam.org/meetings/da13/index.php

Access to Document

10.1137/1.9781611973105.2

http://epubs.siam.org/doi/abs/10.1137/1.9781611973105.2

Cite this

@inproceedings{7366f7c785b94a41831dd44b311dbe23,

title = "Balls into Bins via Local Search",

abstract = "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 Θ(log log n) on expander graphs. In addition, we show that for d-dimensional grids the maximum load is Θ(((log n)/(log log n))(1/(d+1))). Finally, for almost regular graphs with minimum degree Ω(log n), we prove that the maximum load is constant and also reveal a fundamental difference between random and arbitrary tie-breaking rules.",

author = "Paul Bogdan and Thomas Sauerwald and Alexandre Stauffer and He Sun",

year = "2013",

doi = "10.1137/1.9781611973105.2",

language = "English",

isbn = "978-1-61197-251-1",

pages = "16--34",

booktitle = "Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013",

note = "Twenty-Fourth Annual ASM-SIAM Symposium on Discrete Algorithms, SODA 2013 ; Conference date: 06-01-2013 Through 08-01-2013",

url = "http://www.siam.org/meetings/da13/index.php",

}

Bogdan, P, Sauerwald, T, Stauffer, A & Sun, H 2013, Balls into Bins via Local Search. in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013. pp. 16-34, Twenty-Fourth Annual ASM-SIAM Symposium on Discrete Algorithms, New Orleans, United States, 6/01/13. https://doi.org/10.1137/1.9781611973105.2

TY - GEN

T1 - Balls into Bins via Local Search

AU - Bogdan, Paul

AU - Sauerwald, Thomas

AU - Stauffer, Alexandre

AU - Sun, He

PY - 2013

Y1 - 2013

N2 - 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 Θ(log log n) on expander graphs. In addition, we show that for d-dimensional grids the maximum load is Θ(((log n)/(log log n))(1/(d+1))). Finally, for almost regular graphs with minimum degree Ω(log n), we prove that the maximum load is constant and also reveal a fundamental difference between random and arbitrary tie-breaking rules.

AB - 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 Θ(log log n) on expander graphs. In addition, we show that for d-dimensional grids the maximum load is Θ(((log n)/(log log n))(1/(d+1))). Finally, for almost regular graphs with minimum degree Ω(log n), we prove that the maximum load is constant and also reveal a fundamental difference between random and arbitrary tie-breaking rules.

U2 - 10.1137/1.9781611973105.2

DO - 10.1137/1.9781611973105.2

M3 - Conference contribution

SN - 978-1-61197-251-1

SP - 16

EP - 34

BT - Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013

T2 - Twenty-Fourth Annual ASM-SIAM Symposium on Discrete Algorithms

Y2 - 6 January 2013 through 8 January 2013

ER -

Balls into Bins via Local Search

Abstract

Conference

Access to Document

Fingerprint

Cite this