Balanced allocation on graphs
Balanced allocation on graphs
复制标题
DOI：
10.1145/1109557.1109606
复制
发表时间：
2005-10
期刊：
影响因子：
--
通讯作者：
K. Kenthapadi;R. Panigrahy
中科院分区：
文献类型：
--
作者：
K. Kenthapadi;R. Panigrahy
众所周知，如果将 n 个球插入 n 个箱子中，则具有最大负载的箱子很有可能包含 (1 + o(1)) log n/log log n 个球。 Azar、Broder、Karlin 和 Upfal [1] 表明，如果随机选择 d ≥ 2 个箱子，并将球插入到 d 个箱子中负载最少的箱子中，而不是选择一个箱子，则最大负载会急剧减少到 log log n/log d + O(1)。在本文中，我们研究了两个选择球和箱的过程，不允许球选择任何两个随机箱，而只能选择由基础图中的边连接的箱。我们表明，对于 n 个球和 n 个箱子，如果图形几乎是规则的，度数为 nε，其中 ε 不太小，则最大负载的先前界限继续保持。准确地说，最大负载为 log log n + O(1/ε) + O(1)。因此，即使图的度为 nΩ(1/log log n)，最大负载也是 O(log log n)。对于一般的 Δ-正则图，我们表明最大负载为 log log n + O(log n/log (Δ/log4 n)) + O(1)，并且还提供了几乎匹配的 log log n + log n/log (Δ log n) 下界。此外，即使最小度很高，这也不适用于非规则图。Vöcking [29] 表明，通过打破左侧的联系，可以将具有 d 选择负载平衡的最大 bin 大小进一步提高到 O(log log n/d)。这需要 d 个随机 bin 选择。我们证明，这样的界限可以通过仅进行两次随机访问并在每次访问中查询 d/2 个连续的 bin 来实现。通过将 n 个 bin 的序列分为 2n/d 组，每个 d/2 个连续 bin，如果每个球随机选择两个组并将新球插入到负载较小的组中负载最小的 bin 中，则最大负载概率为 O(log log n/d)。此外，事实证明，这种划分为大小为 d/2 的对齐组对于实现此界限也是至关重要的，也就是说，如果我们简单地选择随机但可能未对齐的 d/2 个连续 bin 组，而不是选择两个对齐组，则最大负载会跳至 Ω(log log n/log d)，即使这两个组始终选择不相交。
It is well known that if n balls are inserted into n bins, with high probability, the bin with maximum load contains (1 + o(1)) log n/log log n balls. Azar, Broder, Karlin, and Upfal [1] showed that instead of choosing one bin, if d ≥ 2 bins are chosen at random and the ball in serted into the least loaded of the d bins, the maximum load reduces drastically to log log n/log d + O(1). In this paper, we study the two choice balls and bins process when balls are not allowed to choose any two random bins, but only bins that are connected by an edge in an underlying graph. We show that for n balls and n bins, if the graph is almost regular with degree nε, where ε is not too small, the previous bounds on the maximum load continue to hold. Precisely, the maximum load is log log n + O(1/ε) + O(1). So even if the graph has degree nΩ(1/log log n), the maximum load is O(log log n). For general Δ-regular graphs, we show that the maximum load is log log n + O(log n/log (Δ/log4 n)) + O(1) and also provide an almost matching lower bound of log log n + log n/log (Δ log n). Further this does not hold for non-regular graphs even if the minimum degree is high.Vöcking [29] showed that the maximum bin size with d choice load balancing can be further improved to O(log log n/d) by breaking ties to the left. This requires d random bin choices. We show that such bounds can be achieved by making only two random accesses and querying d/2 contiguous bins in each access. By grouping a sequence of n bins into 2n/d groups, each of d/2 consecutive bins, if each ball chooses two groups at random and inserts the new ball into the least-loaded bin in the lesser loaded group, then the maximum load is O(log log n/d) with high probability. Furthermore, it also turns out that this partitioning into aligned groups of size d/2 is also essential in achieving this bound, that is, instead of choosing two aligned groups, if we simply choose random but possibly unaligned random sets of d/2 consecutive bins, then the maximum load jumps to Ω(log log n/log d) even if the two sets are always chosen to be disjoint.