Communication complexity of approximate maximum matching in the message-passing model
- PDF / 593,630 Bytes
- 17 Pages / 595.276 x 790.866 pts Page_size
- 69 Downloads / 218 Views
Communication complexity of approximate maximum matching in the message-passing model Zengfeng Huang1
· Bozidar Radunovic2 · Milan Vojnovic3 · Qin Zhang4
Received: 29 March 2017 / Accepted: 5 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract 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 graph G that has n vertices and the set of edges partitioned over k sites, and an approximation ratio parameter α. The output is required to be a matching in G that has to be reported by one of the sites, whose size is at least factor α of the size of a maximum matching in G. We show that the communication complexity of this problem is Ω(α 2 kn) information bits. This bound is shown to be tight up to a log n factor, 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. Keywords Approximate maximum matching · Multi-party communication complexity · Message passing
1 Introduction Complex and massive volume data processing requires to scale out to parallel and distributed computation platforms. Scalable distributed computation algorithms are needed that This paper is a revised and extended version of a paper by the same authors that appeared in the Proceedings of the 32nd Symposium on Theoretical Computer Science (STACS), Munich, Germany, March 4– 7, 2015. Q. Zhang: Supported in part by NSF IIS-1633215 and CCF-1844234.
B
Zengfeng Huang [email protected] Bozidar Radunovic [email protected] Milan Vojnovic [email protected] Qin Zhang [email protected]
1
School of Data Science, Fudan University, Shanghai, China
2
Microsoft Research, Cambridge, UK
3
Department of Statistics, London School of Economics (LSE), London, UK
4
Computer Science Department, Indiana University, Bloomington, USA
make efficient use of scarce system resources such as communication bandwidth between compute nodes in order to avoid the communication network becoming a bottleneck. A particular interest has been devoted to studying scalable computation methods for graph data, which arises in a variety of applications including online services, online social networks, biological, and economic systems. In this paper, we consider the distributed computation problem of finding an approximate maximum matching in an input graph whose edges are partitioned over different compute nodes (we refer to as sites). Several performance measures are of interest including the communication complexity in terms of the number of bits or messages, the time complexity in terms of the number of rounds, and the storage complexity in terms of the number of bits. In this paper we focus
Data Loading...
