3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Please use LaTeX to format only equations, not text. There are plenty of formatting options available in this site. $\endgroup$ – dkaeae Aug 6 at 7:03
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ahh I see, so then in the first case, i assume your $1-1/e$ approximation is coming from the submodularity of the objective function. They weren't necessarily meant to be disjoint cases, apologies if i presented them as such. I don't quite understand your comment about the second case yet, but I will go through it in more detail. I just wanted to clarify if that comment holds true when both alterations are made to the problem, and not just the second one? That is, does the comment hold true for the maximum coverage problem, when we need to cover items multiple (2 for now) times? $\endgroup$ – Barcode Aug 6 at 2:52
  • $\begingroup$ Right, the greedy algorithm works for any monotone submodular function. $\endgroup$ – Yuval Filmus Aug 6 at 2:53
  • $\begingroup$ Does your comment hold true when both alterations are taken together? Once you understand my comment, you could attempt to answer it on your own. The end goal is for you to be able to solve your own problems. $\endgroup$ – Yuval Filmus Aug 6 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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