Communication complexity of approximate maximum matching in the message-passing model

Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic and Qin Zhang

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

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 Ω(α2kn)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 (search for similar items in EconPapers)
JEL-codes: C1 (search for similar items in EconPapers)
Pages: 17 pages
Date: 2020-12-01
References: View complete reference list from CitEc
Citations:

Published in Distributed Computing, 1, December, 2020, 33(6), pp. 515 - 531. ISSN: 0178-2770

Downloads: (external link)
http://eprints.lse.ac.uk/103174/ Open access version. (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ehl:lserod:103174

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().