Balls into Bins via Local Search
Thomas Sauerwald ( University of Cambridge )
- 16:00 19th November 2013 ( week 6, Michaelmas Term 2013 )Room 278, Oxford e-Research Centre, 7 Keble Road
We study a natural process for allocating m balls (tasks) into n bins (resources) 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. In this talk we derive bounds on the maximum load of this process and the time until every bin has at least one ball allocated to it.
Speaker bio
Thomas Sauerwald is a lecturer in the Computer Laboratory at the University of Cambridge. He obtained his PhD in Computer Science from the University of Paderborn in 2008. After that, he has held positions at the International Computer Science Institute in Berkeley, Simon Fraser University and Max Planck Institute for Informatics. His main research areas are randomized and distributed algorithms.Share this:
