Communication Complexity of Approximate Matching in Distributed Graphs

被引：11

作者：

Huang, Zengfeng ^{[1
]}

Radunovic, Bozidar ^{[2
]}

Vojnovic, Milan ^{[2
]}

Zhang, Qin ^{[3
]}

机构：

[1] Aarhus Univ, MADALGO, Aarhus, Denmark

[2] Microsoft Res, Cambridge, England

[3] Indiana Univ, Bloomington, IN USA

来源：

32ND INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2015) | 2015年 / 30卷

关键词：

approximate maximum matching; distributed computation; communication complexity;

D O I：

10.4230/LIPIcs.STACS.2015.460

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we consider the communication complexity of approximation algorithms for maximum matching in a graph in the message-passing model of distributed computation. The input graph consists of n vertices and edges partitioned over a set of k sites. The output is an alpha-approximate maximum matching in the input graph which has to be reported by one of the sites. We show a lower bound on the communication complexity of Omega(alpha(2)kn) and show that it is tight up to poly-logarithmic factors. This lower bound also applies to other combinatorial problems on graphs in the message-passing computation model, including max-flow and graph sparsification.

引用

页码：460 / 473

页数：14

共 32 条

[1] Ahn Kook J., 2012, P 23 ANN ACM SIAM S, P459
[2] Ahn KJ, 2011, LECT NOTES COMPUT SC, V6756, P526, DOI 10.1007/978-3-642-22012-8_42
[3] Ahn Kook Jin, 2012, P 31 S PRINCIPLES DA, P5, DOI 10.1145
[4] Ahn KookJin., 2011, CORR
[5] The space complexity of approximating the frequency moments
Alon, N
Matias, Y
Szegedy, M
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 58 (01) : 137 - 147
[6] [Anonymous], MSRTR201335
[7] [Anonymous], 2006, OP PROBL DAT STREAMS
[8] An information statistics approach to data stream and communication complexity
Bar-Yossef, Z
Jayram, TS
Kumar, R
Sivakumar, D
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2004, 68 (04) : 702 - 732
[9] Barak B, 2010, ACM S THEORY COMPUT, P67
[10] A Tight Bound for Set Disjointness in the Message-Passing Model
Braverman, Mark
Ellen, Faith
Oshman, Rotem
Pitassi, Toniann
Vaikuntanathan, Vinod
[J]. 2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, : 668 - 677

← 1 2 3 4 →