Berenbrink, Petra, Friedetzky, Tom, Hu, Zengjian and Martin, R. (Russell). (2008) On weighted balls-into-bins games. Theoretical Computer Science, Vol.409 (No.3). pp. 511-520. ISSN 0304-3975

Full text not available from this repository.

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 > 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
Date:	28 December 2008
Volume:	Vol.409
Number:	No.3
Number of Pages:	10
Page Range:	pp. 511-520
Identification Number:	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:	Related item in WRAP
References:	[1] Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal, Balanced allocations, SIAM Journal on Computing 29 (1) (1999) 180-200. [2] Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking, Balanced allocations: The heavily loaded case, SIAM Journal on Computing 35 (6) (2006) 1350-1385. [3] Petra Berenbrink, Tom Friedetzky, Zengjian Hu, Russell A. Martin, On weighted balls-into-bins games, in: Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science, STACS, 2005, pp. 231-243. [4] Petra Berenbrink, Randomized allocation of independent tasks, University of Paderborn, 2000. [5] Petra Berenbrink, Friedhelm Meyer auf der Heide, Klaus Schröder, Allocating weighted jobs in parallel, Theory of Computing Systems 32 (3) (1999) 281-300. [6] Kunal Talwar, Udi Wieder, Balanced allocations: The weighted case, in: Proc. of the 39th Annual ACM Symposium on Theory of Computing, STOC, 2007, pp. 256-265. [7] Elias Koutsoupias, Marios Mavronicolas, Paul G. Spirakis, Approximate equilibria and ball fusion, Theory of Computing Systems 36 (6) (2003) 683-693. [8] Albert W. Marshall, Ingram Olkin, Inequalities: Theory of Majorization and its Applications, Academic Press, 1979. [9] Michael Mitzenmacher, Andrea W. Richa, Ramesh Sitaraman, The power of two random choices: A survey of techniques and results, in: Handbook of Randomized Computing, 2000. [10] Michael Mitzenmacher, Balaji Prabhakar, Devarat Shah, Load balancing with memory, in: Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2002, pp. 799-808. [11] Peter Sanders, On the competitive analysis of randomized static load balancing, in: Proceedings of the first Workshop on Randomized Parallel Algorithms, RANDOM, 1996. [12] Berthold Vöcking, How asymmetry helps load balancing, Journal of the ACM 50 (4) (2003) 568-589.
URI:	http://wrap.warwick.ac.uk/id/eprint/28817

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item