Balls into Bins: A Sequential Resource Allocation Problem

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

• Ryan Lau, Churchill College
• Wednesday 14 October 2015, 19:00-19:40
• Wolfson Hall, Churchill College.

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.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.