Is there an approximation algorithm for MAX k DOUBLE SET COVER?
(Comment $\rightarrow$ Answer)

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


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}) &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}$$


$\,$


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.