Tight bounds on the round complexity of the distributed maximum coverage problem

Sepehr Assadi, Sanjeev Khanna

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

We study the maximum k-set coverage problem in the follow-ing distributed setting. A collection of input sets S1; : : : ; Sm over a universe [n] is partitioned across p machines and the goal is to find k sets whose union covers the most number of elements. The computation proceeds in rounds where in each round machines communicate information to each other. Specifically, in each round, all machines simultane-ously send a message to a central coordinator who then com-municates back to all machines a summary to guide the com-putation for the next round. At the end of the last round, the coordinator outputs the answer. The main measures of efficiency in this setting are the approximation ratio of the returned solution, the communication cost of each machine, and the number of rounds of computation. Our main result is an asymptotically tight bound on the tradeoff between these three measures for the distributed maximum coverage problem. We first show that any r-round protocol for this problem either incurs a communication cost of k/m(1=r) or only achieves an approximation factor of k(1=r). This in particular implies that any protocol that simultaneously achieves good approximation ratio (O(1) ap-proximation) and good communication cost (eO(n) commu-nication per machine), essentially requires logarithmic (in k) number of rounds. We complement our lower bound result by showing that there exist an r-round protocol that achieves an e e-1 -approximation (essentially best possible) with a com-munication cost of k/mO(1=r) as well as an r-round protocol that achieves a kO(1=r)-approximation with only eO(n) com-munication per each machine (essentially best possible). We further use our results in this distributed setting to obtain new bounds for maximum coverage in two other main models of computation for massive datasets, namely, the dynamic streaming model and the MapReduce model.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages2412-2431
Number of pages20
ISBN (Electronic)9781611975031
DOIs
StatePublished - 2018
Externally publishedYes
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Country/TerritoryUnited States
CityNew Orleans
Period1/7/181/10/18

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Tight bounds on the round complexity of the distributed maximum coverage problem'. Together they form a unique fingerprint.

Cite this