<p>(Comment $\rightarrow$ Answer)</p>

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

<ol>
<li><p>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)$$.</p>

<p>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 </p>

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

<p>$\,$</p>

<ol start="2">
<li>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).$$</li>
</ol>

<p>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),$$</p>

<p>giving an $O(\sqrt{n})$ approximation.</p>

CC BY-SA 3.0
2016-07-17T17:10:05.760Z
Thanks! I guess you used $U$ for what I called $X$. And $n=|\mathcal S|$.
Florent Foucaud
CC BY-SA 3.0
2016-07-18T20:15:26.057Z
$n$ here is $|X|$, which is the same "$n$" as used in the $O(n^{1/4+\epsilon})$ algorithm for Densest $k$-Subgraph.
Yonatan N
CC BY-SA 3.0
2016-07-16T06:31:33.670Z
2016-12-05T18:03:32.980Z
2016-12-05T18:03:32.980Z
Yonatan N
<p>Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ <b>doubly covers</b> a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define the following maximization problem:</p>

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

<p>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 href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.8576" rel="nofollow noreferrer">"A threshold of $\ln n$ for approximating Set Cover"</a>), where a $(1-1/e)$-approximation is given).</p>

<blockquote>
  <p><b>My question:</b> Is there any known nontrivial positive approximation bound for MAX k DOUBLE SET COVER?
  <br>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.180" rel="nofollow noreferrer">this paper</a>).</p>
</blockquote>

<p>As pointed out in the answer to <a href="https://cstheory.stackexchange.com/q/20282/1930">this other question</a>, 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$.<br>
DENSEST k-SUBGRAPH has an $O(n^{1/4})$-approximation algorithm (<a href="http://arxiv.org/abs/1001.2891" rel="nofollow noreferrer">this paper</a>); perhaps this algorithm can been (has been) extended to MAX k DOUBLE SET COVER (for set systems with intersection one)?<br>
(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&lt;1$.)</p>

<p>Any related observation or reference is welcome. Thanks!</p>

CC BY-SA 3.0
2016-01-29T07:31:09.327Z
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 http://sarielhp.org/p/08/multi_cover/multi_cover.pdf . Similar technique might solve your problem for set systems with bounded VC dimension.
Dibyayan
CC BY-SA 3.0
2016-01-29T09:15:29.437Z
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.
Florent Foucaud
CC BY-SA 3.0
2016-02-01T05:16:16.440Z
[An analysis of approximations for maximizing submodular set functions—I](https://scholar.google.com/scholar?cluster=14972013105137272859&hl=en&as_sdt=0,5), 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.
Neal Young
CC BY-SA 3.0
2016-05-30T20:37:03.600Z
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).
Yonatan N
CC BY-SA 3.0
2016-07-12T21:41:44.937Z
@YonatanN, could you please elaborate on your comment? I'd accept this as an answer.
Florent Foucaud
<reference-request><approximation-algorithms><set-cover><hypergraphs><covering-problems>
Is there an approximation algorithm for MAX k DOUBLE SET COVER?
Florent Foucaud
# Is there an approximation algorithm for MAX k DOUBLE SET COVER?

(Asked by: username_0 on 2016-01-28)

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"](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.8576)), 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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.180)).

As pointed out in the answer to [this other question](https://cstheory.stackexchange.com/q/20282/1930), 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](http://arxiv.org/abs/1001.2891)); 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!

**Tags:** reference-request, approximation-algorithms, set-cover, hypergraphs, covering-problems

> **Comments:**
> **username_1**: 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 http://sarielhp.org/p/08/multi_cover/multi_cover.pdf . Similar technique might solve your problem for set systems with bounded VC dimension.  
> **username_0**: 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.  
> **username_2**: [An analysis of approximations for maximizing submodular set functions—I](https://scholar.google.com/scholar?cluster=14972013105137272859&hl=en&as_sdt=0,5), 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.  
> **username_3**: 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).  
> **username_0**: @YonatanN, could you please elaborate on your comment? I'd accept this as an answer.  

---

## 1 answers

### Answer by username_3 on 2016-07-16. Score: 4 | Accepted answer

(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}$$

$\,$

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

> **Comments:**
> **username_0**: Thanks! I guess you used $U$ for what I called $X$. And $n=|\mathcal S|$.  
> **username_3**: $n$ here is $|X|$, which is the same "$n$" as used in the $O(n^{1/4+\epsilon})$ algorithm for Densest $k$-Subgraph.  

---

