Is there an approximation algorithm for MAX k DOUBLE SET COVER?

Question

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!

Answer 1

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