  We study the maximum $k$-set coverage problem in the following distributed
setting. A collection of sets $S_1,\ldots,S_m$ 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 synchronous
rounds. In each round, all machines simultaneously send a message to a central
coordinator who then communicates back to all machines a summary to guide the
computation for the next round. At the end, 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 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 \cdot m^{\Omega(1/r)}$ or only achieves an approximation factor of
$k^{\Omega(1/r)}$. This implies that any protocol that simultaneously achieves
good approximation ratio ($O(1)$ approximation) and good communication cost
($\widetilde{O}(n)$ communication 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
$\frac{e}{e-1}$-approximation (essentially best possible) with a communication
cost of $k \cdot m^{O(1/r)}$ as well as an $r$-round protocol that achieves a
$k^{O(1/r)}$-approximation with only $\widetilde{O}(n)$ communication per each
machine (essentially best possible).
  We further use our results in this distributed setting to obtain new bounds
for the maximum coverage problem in two other main models of computation for
massive datasets, namely, the dynamic streaming model and the MapReduce model.
