Communication complexity of approximate maximum matching in the message-passing model
Communication complexity of approximate maximum matching in the message-passing model
复制标题
消息传递模型中近似最大匹配的通信复杂度
DOI：
10.1007/s00446-020-00371-6
复制
发表时间：
2017-04
影响因子：
1.3
通讯作者：
Zhang Qin
中科院分区：
文献类型：
--
作者：
Huang Zengfeng;Radunovic Bozidar;Vojnovic Milan;Zhang Qin
考虑了在多方消息传递通信模型中寻找图中近似最大匹配的通信复杂度。最大匹配问题是最基本的图组合问题之一，具有多种应用。该问题的输入是一个图，它具有顶点和在站点上划分的边集，以及一个近似比率参数。输出需要是一个匹配的inG，必须由其中一个站点报告，其大小至少是最大匹配inG大小的因数。我们证明了这个问题的通信复杂性是信息位。通过构造算法，确定算法的正确性，并给出通信代价的上界，证明了该上界是紧紧于因子的。下界也适用于消息传递通信模型中的其他图组合问题，包括最大流和图稀疏化。
We consider the communication complexity of finding an approximate maximum matching in a graph in a multi-party message-passing communication model. The maximum matching problem is one of the most fundamental graph combinatorial problems, with a variety of applications. The input to the problem is a graphGthat hasnvertices and the set of edges partitioned overksites, and an approximation ratio parameter. The output is required to be a matching inGthat has to be reported by one of the sites, whose size is at least factorof the size of a maximum matching inG. We show that the communication complexity of this problem isinformation bits. This bound is shown to be tight up to afactor, by constructing an algorithm, establishing its correctness, and an upper bound on the communication cost. The lower bound also applies to other graph combinatorial problems in the message-passing communication model, including max-flow and graph sparsification.
登录
查看更多内容
DOI：
--
发表时间：
2011-04
期刊：
ArXiv
影响因子：
--
作者：
Kook Jin Ahn;S. Guha
通讯作者：
Kook Jin Ahn;S. Guha
影响因子：
5.2
作者：
A. Mcgregor
通讯作者：
A. Mcgregor
DOI：
10.1137/100801901
发表时间：
2009-07
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
L. Epstein;Asaf Levin;Julián Mestre;D. Segev
通讯作者：
L. Epstein;Asaf Levin;Julián Mestre;D. Segev
DOI：
10.1007/978-3-540-30186-8_24
发表时间：
2004-10
期刊：
Colloids and Surfaces A: Physicochemical and Engineering Aspects
影响因子：
--
作者：
Mirjam Wattenhofer;Roger Wattenhofer
通讯作者：
Mirjam Wattenhofer;Roger Wattenhofer
DOI：
10.1109/sfcs.2001.959901
发表时间：
2001-10
期刊：
Proceedings 2001 IEEE International Conference on Cluster Computing
影响因子：
--
作者：
Amit Chakrabarti;Yaoyun Shi;Anthony Wirth;A. Yao
通讯作者：
Amit Chakrabarti;Yaoyun Shi;Anthony Wirth;A. Yao