Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 03, 2015, 12:15 pm
Duration: 45 minutes
Location: OAT S15/S16/S17
Speaker: Lazar Todorovic
We will present the paper "Balls into Bins made Faster" (Megha Khosla, 2013). This paper introduces an algorithm, called "local search allocation", for a specific version of the balls into bins problem defined as follows:
-Each bin can can hold at most one ball.
-Each ball chooses k bins uniformly at random and can only be placed into those bins.
-The goal is to allocate all balls into bins such that the two constraints are not violated.
This definition is relevant in practice as it corresponds to Cuckoo Hashing with k hash functions (k-ways CH).
We will show that the local search allocation algorithm is correct and finds a valid allocation in linear time (with high probability) when there exists one.
Automatic MiSe System Software Version 1.4803M | admin login