The Library
On weighted balls-into-bins games
Tools
Berenbrink, Petra, Friedetzky, Thomas, Hu, Zengjian and Martin, R. (2008) On weighted balls-into-bins games. Theoretical Computer Science, Vol.409 (No.3). pp. 511-520. doi:10.1016/j.tcs.2008.09.023 ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.tcs.2008.09.023
Abstract
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. (C) 2008 Elsevier B.V. All rights reserved.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Game theory, Probabilities, Computer algorithms, Resource allocation -- Mathematical models, Mathematical optimization | ||||
Journal or Publication Title: | Theoretical Computer Science | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0304-3975 | ||||
Official Date: | 28 December 2008 | ||||
Dates: |
|
||||
Volume: | Vol.409 | ||||
Number: | No.3 | ||||
Number of Pages: | 10 | ||||
Page Range: | pp. 511-520 | ||||
DOI: | 10.1016/j.tcs.2008.09.023 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Version or Related Resource: | Berenbrink, P., Friedetzky, T., Hu, Z., Martin, R.A. (2005). On weighted balls-into-bins games, in: Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science, STACS, 2005, pp. 231-243. http://wrap.warwick.ac.uk/id/eprint/6981 | ||||
Related URLs: |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |