5
$\begingroup$

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

$\endgroup$
  • $\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 Rasberry Apr 3 '17 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$ – lchen Apr 3 '17 at 9:54
1
$\begingroup$

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*}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you Thomas. Do you have any idea on possible approximation algorithm ($O(1)$ or even $O(log)$)? $\endgroup$ – lchen Apr 4 '17 at 8:18
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you zeb. I will take the time digesting your comments. $\endgroup$ – lchen Apr 4 '17 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.