Department of Computer Science
University of Durham
4pm Tuesday 22nd March 2005
Room 2511, JCMB, King's Buildings
We consider the well-known problem of randomly allocating m balls into n bins.
We give a brief introduction to analytical techniques that are being used in this area, after which we investigate various properties of single-choice games as well as multiple-choice games in the context of weighted balls. We are particularly interested in questions that are concerned with the distribution of ball weights, and the order in which balls are allocated. Do any of these parameters influence the maximum expected load of any bin, and if yes, then how?
The problem of weighted balls is of practical relevance. Balls-into-bins games are frequently used to conveniently model load balancing problems. Here, weights can be used to model resource requirements of the jobs, i.e., memory or running time.
Joint work with Petra Berenbrink, Zengjian Hu, and Russell Martin.