论文标题
填充平衡分配的力量
The Power of Filling in Balanced Allocations
论文作者
论文摘要
我们介绍了一类新的平衡分配过程，这些过程主要以``填充''的垃圾箱为特征。一个典型的例子是包装过程：在每一轮中，我们只服用一个垃圾箱样品，如果负载低于平均负载，那么我们将尽可能多的球放置在达到平均负载之前。否则，我们只放一个球。我们证明，对于此类中的任何过程，最大负载和平均负载之间的差距为$ \ MATHCAL {O}（\ log n）$ W.H.P.对于任何数量的球$ m \ geq 1 $。对于包装过程，我们还提供了匹配的下限。此外，我们证明了包装过程的样本有效，因为每个样品分配的球的预期球数严格大于一个。最后，我们还证明了间隙上$ \ Mathcal {O}（\ log n）$的上限可以扩展到Mitzenmacher，Prabhakar和Shah（2002）研究的内存过程。
We introduce a new class of balanced allocation processes which are primarily characterized by ``filling'' underloaded bins. A prototypical example is the Packing process: At each round we only take one bin sample, if the load is below the average load, then we place as many balls until the average load is reached; otherwise, we place only one ball. We prove that for any process in this class the gap between the maximum and average load is $\mathcal{O}(\log n)$ w.h.p. for any number of balls $m\geq 1$. For the Packing process, we also provide a matching lower bound. Additionally, we prove that the Packing process is sample-efficient in the sense that the expected number of balls allocated per sample is strictly greater than one. Finally, we also demonstrate that the upper bound of $\mathcal{O}(\log n)$ on the gap can be extended to the Memory process studied by Mitzenmacher, Prabhakar and Shah (2002).
