Personal tools
You are here: Home Events Abstract Archives 2005 On Weighted Balls-into-bins Games

On Weighted Balls-into-bins Games

Tom Friedetzky 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.

Document Actions