Distributed Sparse Cut Approximation
Distributed Sparse Cut Approximation
复制标题
分布式稀疏割逼近
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. R. Molla
中科院分区：
文献类型：
--
作者：
F. Kuhn;A. R. Molla
我们研究在无向网络图 G=(V,E) 中计算稀疏割的问题。我们通过电导 phi(S) 来测量切口 (S,VS) 的稀疏性，即通过穿过切口的边数与两侧较小边的度数之和的比率。我们提出了一种有效的分布式算法来计算低电导率的切割。具体来说，给定两个参数 b 和 phi，如果存在至少 b 的平衡截止和至多 phi 的电导，我们的算法输出至少 b/2 的平衡截止和至多 ~O(sqrt{phi}) 的电导，其中 ~O(.) 隐藏节点数量 n 中的多对数因子。我们的分布式算法工作在拥塞模型中，即它只需要发送大小最多为 O(log(n)) 位的消息。该算法的时间复杂度为 ~O(D + 1/b*phi)，其中 D 是 G 的直径。这比 Das Sarma 等人的结果有显着改进。 [ICDCN 2015]，其中表明可以在 ~O(n + 1/b*phi) 时间内计算出相同质量的切割。运行时间的改进尤其是通过设计和应用一种高效的分布式算法来解决分布式搜索树中的所有前缀和问题来实现的。该算法基于经典的并行全前缀和算法，可能具有独立的意义。
We study the problem of computing a sparse cut in an undirected network graph G=(V,E). We measure the sparsity of a cut (S,VS) by its conductance phi(S), i.e., by the ratio of the number of edges crossing the cut and the sum of the degrees on the smaller of the two sides. We present an efficient distributed algorithm to compute a cut of low conductance. Specifically, given two parameters b and phi, if there exists a cut of balance at least b and conductance at most phi, our algorithm outputs a cut of balance at least b/2 and conductance at most ~O(sqrt{phi}), where ~O(.) hides polylogarithmic factors in the number of nodes n. Our distributed algorithm works in the congest model, i.e., it only requires to send messages of size at most O(log(n)) bits. The time complexity of the algorithm is ~O(D + 1/b*phi), where D is the diameter of G. This is a significant improvement over a result by Das Sarma et al. [ICDCN 2015], where it is shown that a cut of the same quality can be computed in time ~O(n + 1/b*phi). The improved running time is in particular achieved by devising and applying an efficient distributed algorithm for the all-prefix-sums problem in a distributed search tree. This algorithm, which is based on the classic parallel all-prefix-sums algorithm, might be of independent interest.