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$.
2
-
$\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 RasberryCommented Apr 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$– lchenCommented Apr 3, 2017 at 9:54
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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*}
answered Apr 3, 2017 at 22:01
-
$\begingroup$ Thank you Thomas. Do you have any idea on possible approximation algorithm ($O(1)$ or even $O(log)$)? $\endgroup$– lchenCommented Apr 4, 2017 at 8:18
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Thank you zeb. I will take the time digesting your comments. $\endgroup$– lchenCommented Apr 4, 2017 at 15:51
$\begingroup$
$\endgroup$
Regarding your second question. There is a (1/2)-approximation algorithm for your problem.
In detail, the input consists of k collections of subsets of a given universe. The goal is to select exactly one subset from each collection to maximize the number of covered elements. The algorithm is a generalization of the classical greedy algorithm for the canonical maximum coverage problem:
- Initially, all elements are uncovered.
- Select the subset that covers as many uncovered elements as possible.
- Remove the collection from where the previous subset was taken.
- Update the set of covered elements.
- If no more collections exist, return the k subsets selected; otherwise, go to step 2.
