On weighted balls-into-bins games
Berenbrink, Petra, Friedetzky, Thomas, Hu, Zengjian and Martin, R. (2005) On weighted balls-into-bins games. In: STACS 2005, Stuttgart, Germany, Feb 24-26, 2005. Published in: Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science, Vol.3404 pp. 231-243.Full text not available from this repository.
We consider the well-known problem of randomly allocating m balls into n bins. 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.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics
Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
|Divisions:||Faculty of Science > Computer Science|
|Library of Congress Subject Headings (LCSH):||Game theory, Probabilities, Computer algorithms, Resource allocation -- Mathematical models, Mathematical optimization|
|Series Name:||Lecture notes in computer science|
|Journal or Publication Title:||Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science|
|Editor:||Diekert, Volker, 1955- and Durand, B.|
|Official Date:||February 2005|
|Number of Pages:||13|
|Page Range:||pp. 231-243|
|Version or Related Resource:||Berenbrink, P., et al. (2008). On weighted balls-into-bins games. Theoretical Computer Science, 409(3), pp. 511-520. http://wrap.warwick.ac.uk/id/eprint/28817|
|Title of Event:||STACS 2005|
|Type of Event:||Conference|
|Location of Event:||Stuttgart, Germany|
|Date(s) of Event:||Feb 24-26, 2005|
Actions (login required)