Randomized diffusion for indivisible loads
Randomized diffusion for indivisible loads
复制标题
DOI：
10.1016/j.jcss.2014.04.027
复制
发表时间：
2015-02-01
影响因子：
1.1
通讯作者：
Sauerwald, Thomas
中科院分区：
文献类型：
--
作者：
Berenbrink, Petra;Cooper, Colin;Sauerwald, Thomas
提出了一种基于随机扩散的网络不可分任务(令牌)均衡算法。我们的目标是最大限度地减少最大和最小负荷之间的差异。该算法的工作原理如下。每个顶点在其邻居和自身之间尽可能平均地分配其令牌。如果在不拆分某些令牌的情况下这是不可能的，则顶点将在其所有邻居之间随机地重新分配其多余的令牌(无需替换)。本文证明了一般网络负载差异的几个上界。这些界依赖于网络的一些扩展性质，即第二大特征值，以及一种新的度量，我们称之为精化局部发散度。然后，我们应用这些一般界来获得某些特定网络的结果。对于常数度扩张器和环面图，它们在差异界上产生了指数级的改进。为。我们得到了一个多项式的改进。(C)2014 Elsevier Inc.保留所有权利。
We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds. For. hypercubes we obtain a polynomial improvement. (c) 2014 Elsevier Inc. All rights reserved.