On weighted balls-into-bins games
On weighted balls-into-bins games
复制标题
DOI：
10.1016/j.tcs.2008.09.023
复制
发表时间：
2005-02
期刊：
影响因子：
--
通讯作者：
P. Berenbrink;T. Friedetzky;Zengjian Hu;R. Martin
中科院分区：
文献类型：
--
作者：
P. Berenbrink;T. Friedetzky;Zengjian Hu;R. Martin
我们考虑众所周知的问题，随机分配到n箱m球。我们调查的各种性质的单选游戏以及多项选择游戏的背景下，加权球。我们特别感兴趣的问题是有关分配球的重量，并在其中分配球的顺序。这些参数中是否有任何一个会影响任何垃圾箱的最大预期装载量，如果有，那么是如何影响的？配重球的问题具有实际意义。球进箱子游戏经常被用来方便地建模负载平衡问题。这里，权重可以用于对作业的资源需求进行建模，即，内存或运行时间。
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.