On weighted balls-into-bins games
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. ISSN 0304-3975Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.tcs.2008.09.023
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 > 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|
|Official Date:||28 December 2008|
|Number of Pages:||10|
|Page Range:||pp. 511-520|
|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|
 Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal, Balanced allocations, SIAM Journal on Computing 29 (1) (1999) 180-200.
Actions (login required)