A variant of set cover problem reformulated Given a universe set $U$ and $n$ sets of sets $A_i$ ($i=1, \cdots, n$). Each set $A_i$ contains $k_i$ subsets of $U$, i.e., $A_i=\{B_{ij}: j=1, \cdots, k_i\}$ where $B_{ij}$ is a subset of $U$. I have two questions. The first one is to find the minimum number of such $B_{i,j}$ to cover $U$ under the constraint that I can pick at most one such $B_{i,j}$ in each $A_i$. If such solution does not exist, my second question is to choose one set $B_{ij}$ from each set $A_i$ such that the union of the chosen sets covers the maximum number of elements in $U$. 
 A: The decision problem "Can $U$ be covered by sets $B_{ij}$ such that at most one set from each $A_i$ is used?" is NP-complete, and the optimization problem is APX-hard (there is a constant $c$ such that finding a $(1+c)$-approximation is NP-hard). This can be proved by reduction from 3-dimensional matching. Let $U=X\cup Y\cup Z$, and let the 3-DM instance be given by a set $T\subseteq X\times Y\times Z$. The corresponding instance of your problem has $n=\lvert U\rvert$, and the given collection of sets coonsists of the following:
\begin{align*}
A_x &= \{\{x,y,z\}\ :\ (x,y,z)\in T\} && x\in X,\\
A_y &= \{\{x,y,z\}\ :\ (x,y,z)\in T\} && y\in Y,\\
A_z &= \{\{x,y,z\}\ :\ (x,y,z)\in T\} && z\in Z.
\end{align*}
A: The paper Maximizing a Monotone Submodular Function subject to a Matroid Constraint gives a $(1-1/e)$-approximation algorithm for a generalized version of your second question. Even in the case where all the $A_i$s are equal to each other, this approximation ratio is best possible under the assumption $P \ne NP$.
In order to put your second question into their framework, we set $X = \{B_{ij} : i \le n, j \le k_i\}$, define the monotone submodular function $f : 2^X \rightarrow \mathbb{R}_+$ by $f(S) = |\cup_{B_{ij} \in S} B_{ij}|$, and we define the matroid $\mathcal{M} = (X,I)$ to be a partition matroid: $S \subseteq X$ is independent iff $|S \cap A_i| \le 1$ for $i = 1, ..., n$. Then your goal is to maximize $f(S)$ over over the independent sets $S \in I$.
Full disclosure: Jan Vondrak told me about this result (and this particular special case) a few weeks ago when I asked him for advice on solving a variation on your problem.
