  This paper studies the set cover problem under the semi-streaming model. The
underlying set system is formalized in terms of a hypergraph $G = (V, E)$ whose
edges arrive one-by-one and the goal is to construct an edge cover $F \subseteq
E$ with the objective of minimizing the cardinality (or cost in the weighted
case) of $F$. We consider a parameterized relaxation of this problem, where
given some $0 \leq \epsilon < 1$, the goal is to construct an edge $(1 -
\epsilon)$-cover, namely, a subset of edges incident to all but an
$\epsilon$-fraction of the vertices (or their benefit in the weighted case).
The key limitation imposed on the algorithm is that its space is limited to
(poly)logarithmically many bits per vertex.
  Our main result is an asymptotically tight trade-off between $\epsilon$ and
the approximation ratio: We design a semi-streaming algorithm that on input
graph $G$, constructs a succinct data structure $\mathcal{D}$ such that for
every $0 \leq \epsilon < 1$, an edge $(1 - \epsilon)$-cover that approximates
the optimal edge \mbox{($1$-)cover} within a factor of $f(\epsilon, n)$ can be
extracted from $\mathcal{D}$ (efficiently and with no additional space
requirements), where \[ f(\epsilon, n) = \left\{ \begin{array}{ll} O (1 /
\epsilon), & \text{if } \epsilon > 1 / \sqrt{n} \\ O (\sqrt{n}), &
\text{otherwise} \end{array} \right. \, . \] In particular for the traditional
set cover problem we obtain an $O(\sqrt{n})$-approximation. This algorithm is
proved to be best possible by establishing a family (parameterized by
$\epsilon$) of matching lower bounds.
