Is this variation of set-cover NP-hard to approximate?

Question

The classic set-cover problem is described as follows:

Let $S = \{s_1, ..., s_n\}$ be a target set, and let $\Lambda = \{A_1, ..., A_m: A_i \subset S\}$ be a collection of subsets of $S$. The objective is to find some cover $C \subset \Lambda $ such that $\cup_{A\in C}A = S$ and $|C|$ is minimized. That is, find the minimum number of $A$'s needed to cover every element of $S$.

The variation we will consider has two key alterations:

1. Rather than finding some cover $C$ such that $|C|$ is minimized, we want to cover as much of $S$ as possible, given some budget $k$. That is, let $F\subset S$ be the elements that are covered by $C$, our objective is to maximize $$\big|F \cap S\big|$$ such that $|C| \leq k$.

2. Rather than considering an element $s \in S$ covered when $s$ appears in at least one $A\in C$, we require that $s$ show up in 2 distinct $A$'s to be considered covered. (Any multiple is also interesting, even heterogeneous ones for each $s\in S$, but for now 2 is good enough).

So far I can show that it is an NP optimization (reduction from set-cover), and that a $n-$approximation exists by simply looking any element $s$ that appears in some $A_i$ and $A_j$ and then selecting $C = \{A_i, A_j\}$, but this is a rather unsatisfying approximation.

Is this variation NP-hard to approximate to a constant factor?

Answer 1

Your first problem is a classical NP-hard problem known as maximum coverage. The greedy algorithm gives a $1-1/e$ approximation, and this is tight (assuming P≠NP).

Your second problem is a special case of set cover. Indeed, take any instance of set cover, and add to it the set $S$ itself. If the optimal solution for the set cover instance is $M$, then the optimal solution for the new instance (of your problem) is either $M$ or $M+1$. (You can also add $S \cup \{x\},\{x\}$, where $x$ is a new element, to make the optimal solution of the new instance exactly $M+2$.) Hence your problem inherits the $\ln n$-hardness of set cover. In the other direction, the greedy algorithm likely gives an $O(\log n)$ approximation for your problem.