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$.

$\begingroup$ It seems like you have two tasks stated rather than questions  are you seeking an algorithm that does this as efficiently as possible? The setup is of interest to me, but as stated currently, I could be flip and say that you could simply exhaust all possible selections until you get a cover, and if you don't get a cover, go back over the list and see which selection(s) came the closest. $\endgroup$– Thomas RasberryApr 3, 2017 at 9:30

$\begingroup$ @ThomasRasberry Thank you for the comment. Yes, I am seeking an efficient algorithm with polynomial complexity achieving bounded approximation ratio. Your algorithm is of exponential complexity. $\endgroup$– lchenApr 3, 2017 at 9:54
2 Answers
The decision problem "Can $U$ be covered by sets $B_{ij}$ such that at most one set from each $A_i$ is used?" is NPcomplete, and the optimization problem is APXhard (there is a constant $c$ such that finding a $(1+c)$approximation is NPhard). This can be proved by reduction from 3dimensional matching. Let $U=X\cup Y\cup Z$, and let the 3DM 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*}

$\begingroup$ Thank you Thomas. Do you have any idea on possible approximation algorithm ($O(1)$ or even $O(log)$)? $\endgroup$– lchenApr 4, 2017 at 8:18
The paper Maximizing a Monotone Submodular Function subject to a Matroid Constraint gives a $(11/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.

$\begingroup$ Thank you zeb. I will take the time digesting your comments. $\endgroup$– lchenApr 4, 2017 at 15:51