University of Cambridge > Talks.cam > Churchill CompSci Talks > Balls into Bins: A Sequential Resource Allocation Problem

Balls into Bins: A Sequential Resource Allocation Problem

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Matthew Ireland.

Sequential resource allocation problems arise naturally in computer science. For example, load balancing can be viewed as an instance of such problem. Therefore, there is general interest from the community in methods for distributing resources evenly, robustly and efficiently. This presentation introduces the balls into bins model as an abstract characterization of such problems. Different allocation strategies will be discussed and contrasted, with an emphasis on randomized allocations such as the one-choice and the d­choice processes. We shall show that the latter, being a simple generalization of the former, does possess the three properties we seek for allocation algorithms. Perhaps surprisingly, these theoretical results can be applied to drastically optimise the performance of hash tables.

This talk is part of the Churchill CompSci Talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2018 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity