  We consider the Max Unique Coverage problem, including applications to the
data stream model. The input is a universe of $n$ elements, a collection of $m$
subsets of this universe, and a cardinality constraint, $k$. The goal is to
select a subcollection of at most $k$ sets that maximizes unique coverage, i.e,
the number of elements contained in exactly one of the selected sets. The Max
Unique Coverage problem has applications in wireless networks, radio broadcast,
and envy-free pricing.
  Our first main result is a fixed-parameter tractable approximation scheme
(FPT-AS) for Max Unique Coverage, parameterized by $k$ and the maximum element
frequency, $r$, which can be implemented on a data stream. Our FPT-AS finds a
$(1-\epsilon)$-approximation while maintaining a kernel of size $\tilde{O}(k
r/\epsilon)$, which can be combined with subsampling to use $\tilde{O}(k^2 r /
\epsilon^3)$ space overall. This significantly improves on the previous-best
FPT-AS with the same approximation, but a kernel of size $\tilde{O}(k^2 r /
\epsilon^2)$. In order to achieve our result, we show upper bounds on the ratio
of a collection's coverage to the unique coverage of a maximizing
subcollection; this is by constructing explicit algorithms that find a
subcollection with unique coverage at least a logarithmic ratio of the
collection's coverage. We complement our algorithms with our second main
result, showing that $\Omega(m / k^2)$ space is necessary to achieve a $(1.5 +
o(1))/(\ln k - 1)$-approximation in the data stream. This dramatically improves
the previous-best lower bound showing that $\Omega(m / k^2)$ is necessary to
achieve better than a $e^{-1+1/k}$-approximation.
