5
$\begingroup$

Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define the following maximization problem:

MAX k DOUBLE SET COVER
INPUT: a set system $(X,\mathcal S)$, an integer $k$
OUTPUT: a set $\mathcal C\subseteq \mathcal S$, $|\mathcal C| \le k$
MEASURE: the number of elements of $X$ that are doubly covered by $\mathcal C$

MAX k DOUBLE SET COVER is a generalization of the problem MAX k SET COVER, where we only require simple coverage instead of double coverage (see the celebrated 1998 paper by Feige, "A threshold of $\ln n$ for approximating Set Cover"), where a $(1-1/e)$-approximation is given).

My question: Is there any known nontrivial positive approximation bound for MAX k DOUBLE SET COVER?
Note: I am especially interested in the restriction where the set system has maximum intersection one, that is, any two sets in $\mathcal S$ share at most one element (SET COVER for these set systems remains hard to approximate, see this paper).

As pointed out in the answer to this other question, the problem DENSEST k-SUBGRAPH is a special instance restriction of MAX k DOUBLE SET COVER with set systems with intersection one: an input graph $G$ corresponds to the hypergraph $(E(G),\mathcal S_G)$ where $\mathcal S_G$ has a set $S_v$ for each vertex $v$ of $V(G)$ containing the edges incident to $v$ in $G$.
DENSEST k-SUBGRAPH has an $O(n^{1/4})$-approximation algorithm (this paper); perhaps this algorithm can been (has been) extended to MAX k DOUBLE SET COVER (for set systems with intersection one)?
(The complexity of DENSEST k-SUBGRAPH being well-studied and a tough open problem, for MAX k DOUBLE SET COVER I am not expecting anything better than an approximation ratio of the form $O(n^{\delta})$ for some $\delta<1$.)

Any related observation or reference is welcome. Thanks!

$\endgroup$
  • $\begingroup$ K-Multi set cover problem (where each element in the ground set must be covered by at least K sets) is a special case of MAX k DOUBLE SET COVER. For set systems with bounded VC dimension the K-Multi set cover problem have better algorithms. See the paper in sarielhp.org/p/08/multi_cover/multi_cover.pdf . Similar technique might solve your problem for set systems with bounded VC dimension. $\endgroup$ – Dibyayan Jan 29 '16 at 7:31
  • $\begingroup$ Thanks, but the problem you refer to is a minimization problem (find a minimum-size k-multi set cover that covers ALL elements), while my problem is a maximization problem. This makes them quite different. As a related example, MIN SET COVER has no $o(\log n)$ approximation, while MAX k SET COVER has a $(1-1/e)$-approximation. Similar differences exist between e.g. the graph problems MIN VERTEX COVER and MAX k-VERTEX COVER. $\endgroup$ – Florent Foucaud Jan 29 '16 at 9:15
  • $\begingroup$ An analysis of approximations for maximizing submodular set functions—I, by Nemhauser and Wolsey, 1978.. see section 4 for a (1-1/e)-approximation generalizing the well-known (1-1/e)-approximation algorithm for maximum coverage. Except your underlying function is not quite submodular! So this is not what you want. $\endgroup$ – Neal Young Feb 1 '16 at 5:16
  • 2
    $\begingroup$ There is a simple O(√n) approximation algorithm for the problem when n =def |U|. You get it by combining taking the largest of either the |S| greedy Max-(k-1)-cover solutions induced on elements from any one of the |S| sets (the best of which is a k/(1-1/e) approximation) and the union of k/2 pairs of sets which cover at least one element per pair (which gives a 2n/k approximation). $\endgroup$ – Yonatan N May 30 '16 at 20:37
  • $\begingroup$ @YonatanN, could you please elaborate on your comment? I'd accept this as an answer. $\endgroup$ – Florent Foucaud Jul 12 '16 at 21:41
5
$\begingroup$

(Comment $\rightarrow$ Answer)

Consider the following algorithms for a hypergraph $(U,\mathcal S)$, with $n=|U|$:

  1. For a set $X\subseteq \mathcal S$ of sets and a set $A \in X$, define $d_X(A)$ as the number of elements in $A$ that are double covered by $X$, i.e. $|A \cap \left(\bigcup(X \setminus \{A\})\right|$. Additionally, let $c(X)$ denote the number of elements double covered by $X$. By simple counting arguments, $$\max_{A \in X} d_X(A) \leq c(X) \leq \tfrac{1}{2}\sum_{A \in X} d_{X}(A)$$.

    Now do the following for each set $A \in \mathcal{S}$: fix your choice of $A$ as one of the sets in your candidate solution. Now consider the Max-$(k-1)$-cover problem with set system $\mathcal{S} \setminus \{A\}$ and universe $A$. Let $X$ be the output of the greedy algorithm for this Max-$(k-1)$-cover problem, which approximates the optimal solution to within a factor of $1-1/e$. Call this greedy solution $Y_A$, and consider the candidate solution $X_A = Y_A \cup \{A\}$. Call the best such solution $Z$. For each $A \in \mathrm{OPT}$, the solution generated this way satisfies (by the guarantee of the greedy algorithm) $$d_{X_A}(A)/(1-1/e) \geq \max_{\stackrel{T \subseteq S}{|T|=k-1}} d_{T\cup\{A\}}(A) \geq d_{\mathrm{OPT}}(A)$$. Now, letting $B$ be the set in $\mathrm{OPT}$ maximizing $d_\mathrm{OPT}(B)$, we have

    $$\begin{eqnarray} c(\mathrm{OPT}) & \leq & \tfrac{1}{2}\sum_{A \in \mathrm{OPT}} d_{\mathrm{OPT}}(A) \\ & \leq & \tfrac{k}{2}d_\mathrm{OPT}(B) \\ & \leq & \tfrac{k}{2-2/e} d_{X_B}(B) \\ & \leq & \tfrac{k}{2-2/e} \max_{A \in X_B} d_{X_B}(A) \\ & \leq & \tfrac{k}{2-2/e} c(X_B) \\ & \leq & \tfrac{k}{2-2/e}c(Z). \end{eqnarray}$$

$\,$

  1. First, remove from $U$ all elements that can't possibly be double covered. Initialize $Y = \emptyset$. While $|Y| \leq k$ (and $Y$ doesn't fully double cover $U$), arbitrarily pick an element $x \in U$. We then add sets containing $x$ to $Y$ (chosen arbitrarily) until $Y$ at least double covers $x$. When the loop terminates, return $Y$. The total number of elements double covered this way ($c(Y)$) is at least $\min(|U|, k/2)$. If it's $|U|$, we solved the problem exactly so there's no need for further analysis. Otherwise, we have $$c(\mathrm{OPT}) \leq n = \tfrac{2n}{k} \cdot k/2 \leq \tfrac{2n}{k} \cdot c(Y).$$

Now run the two above algorithms, generating solutions $Z$ and $Y$, and let $X = \max(Y, Z)$. Multiplying the two inequalities, $$c(\mathrm{OPT})^2 \leq \tfrac{k}{(2-2/e)} \tfrac{2n}{k} \cdot c(Y)c(Z) = \tfrac{n}{1-1/e} c(Y)c(Z) \leq \tfrac{n}{1-1/e} c(X)^2.$$ So $$c(\mathrm{OPT}) \leq \sqrt{\tfrac{n}{1-1/e}} c(X),$$

giving an $O(\sqrt{n})$ approximation.

$\endgroup$
  • $\begingroup$ Thanks! I guess you used $U$ for what I called $X$. And $n=|\mathcal S|$. $\endgroup$ – Florent Foucaud Jul 17 '16 at 17:10
  • $\begingroup$ $n$ here is $|X|$, which is the same "$n$" as used in the $O(n^{1/4+\epsilon})$ algorithm for Densest $k$-Subgraph. $\endgroup$ – Yonatan N Jul 18 '16 at 20:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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