patternMinor
Is this variation of set-cover NP-hard to approximate?
Viewed 0 times
thisapproximatehardvariationcoverset
Problem
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:
-
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$.
-
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?
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:
-
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$.
-
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#112479, answer score: 3
Revisions (0)
No revisions yet.