Balls into Bins via Local Search

Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, He Sun

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish
Title of host publicationProceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013
Pages16-34
Number of pages19
ISBN (Electronic)978-1-61197-310-5
DOIs
Publication statusPublished - 2013
EventTwenty-Fourth Annual ASM-SIAM Symposium on Discrete Algorithms - Astor Crowne Plaza Hotel, New Orleans, United States
Duration: 6 Jan 20138 Jan 2013
http://www.siam.org/meetings/da13/index.php

Conference

ConferenceTwenty-Fourth Annual ASM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA 2013
Country/TerritoryUnited States
CityNew Orleans
Period6/01/138/01/13
Internet address

Fingerprint

Dive into the research topics of 'Balls into Bins via Local Search'. Together they form a unique fingerprint.

Cite this