<p>This answers question (2):</p>

<p>The greedy heuristic for Set Cover / Maximum Coverage always picks the set which contains the maximal number of uncovered elements.</p>

<p>Assuming your modification for the heuristic is picking the set which greedily increases the solution profit, you might end up in a lousy approximation ratio.</p>

<p>Consider the following example:
$$A = \{a_1,a_2,\ldots a_{k}\}, B=\{b_1,b_2,\ldots b_k\}$$
$$C = \{C_1\} \cup C_2$$
$$C_1= A\cup B \setminus\{b_1\}$$
$$ C_2 = \{\{a_{i},b_1\}|i\in[k]\}$$</p>

<p>The greedy heuristic will output $C'=\{C_1\}$, so the profit is $1$, while the optimal solution is $C_2$ which gives profit $k-1$.</p>

CC BY-SA 3.0
2014-10-08T08:23:05.643Z
Thanks for your answer...very useful to have a concrete example! I've added my own answer below which you might be interested in.
sammy34
CC BY-SA 3.0
2014-10-08T08:34:08.230Z
@sammy34 - read it (and upvoted :) ). I've found this problem interesting and I'll take a look at the papers in the answer.
btw, There's nothing wrong in answering your own question.
R B
CC BY-SA 3.0
2014-10-07T15:48:35.253Z
2014-10-07T15:48:35.253Z
R B
<p>Sorry for answering my own question, but I found the answer quite clearly.</p>

<p>To question 1: It turns out that this problem <a href="http://www.sciencedirect.com/science/article/pii/S0020019008001592" rel="nofollow">has been studied by Pauli Miettinen</a> not too long ago. The intuitive name given to it is "The Positive-Negative Partial Set Cover problem".</p>

<p>To question 2: Although the adapted trivial heuristic (each time picking the set which greedily increases the solution profit) is not discussed in the paper, Miettinen (in Corollary 3) tells us the following:</p>

<p><em>There exists a polynomial-time approximation algorithm for the Positive-Negative Partial Set Cover problem that achieves an approximation factor of $2 \sqrt{\left(m + \pi\right) \log \pi}$, where $m$ and $\pi$ relate to the related approximation of the Red-Blue Set Cover problem (see the paper).</em></p>

<p>The polynomial-time algorithm he references is that <a href="http://www.sciencedirect.com/science/article/pii/S1570866706000189" rel="nofollow">given in Peleg</a>, which I'm now off to try to understand :).</p>

<p>I thank you all for your contributions and comments!!</p>

<p><strong>UPDATE</strong></p>

<p>So, the plot thickens. Neal Young kindly and correctly pointed out that Miettinen's objective function is different to mine (see comments). Verbosely...</p>

<p>Understanding my original $A$ set to be the elements we generally <em>do</em> want covered, and my original $B$ set to be the elements we generally <em>don't</em> want covered, we understand <em>my</em> objective function as maximizing (same as in my initial post)</p>

<p>$\left| \left(\bigcup\limits_{c \in C'} c \right) \cap A \right| - \left| \left(\bigcup\limits_{c \in C'} c \right) \cap B \right|$.</p>

<p>This is equivalent to <em>minimizing</em> (Miettinen minimizes cost rather than maximizing profit)</p>

<p>$\left| \left(\bigcup\limits_{c \in C'} c \right) \cap B \right| - \left| \left(\bigcup\limits_{c \in C'} c \right) \cap A \right|$.</p>

<p>With a bit of manipulation</p>

<p>$\left| \left(\bigcup\limits_{c \in C'} c \right) \cap B \right| - \left| \left(\bigcup\limits_{c \in C'} c \right) \cap A \right| + \left( \left| A \setminus \left(\bigcup\limits_{c \in C'} c \right) \right| - \left| A \setminus \left(\bigcup\limits_{c \in C'} c \right) \right| \right)$</p>

<p>$\Leftrightarrow \left( \left| A \setminus \left(\bigcup\limits_{c \in C'} c \right) \right| + \left| \left(\bigcup\limits_{c \in C'} c \right) \cap B \right| \right) - \left| A \right|$</p>

<p>we see that (the minimization form of) my objective function <em>plus</em> $\left|A\right|$ is equivalent to Miettinen's objective function (in parentheses).</p>

<p>Miettinen's objective function is not exactly what I'm looking for. Actually, all this has made me realise that even my objective function isn't exactly in line with my objective (oh dear)! I'm going to take a step back, reformulate, and ask a separate question if required. Again, thank you all for your help.</p>

CC BY-SA 3.0
2014-10-08T16:21:56.120Z
Taking a look at Miettinen's paper, isn't the objective function different than in your problem?  His objective is yours, plus |B|.  That is, his objective counts the number of covered elements in A, plus the number of uncovered elements in B.  His objective is equivalent to yours w.r.t. exact optimization, but not w.r.t. multiplicative-factor approximation.  (His is easier to approximate.)
Neal Young
CC BY-SA 3.0
2014-10-09T08:38:47.320Z
Thank you so much for picking me up on this. I've updated my answer.
sammy34
CC BY-SA 3.0
2014-10-08T08:14:58.420Z
2014-10-09T08:38:22.613Z
2014-10-09T08:38:22.613Z
sammy34
<p>I am trying to give a <strong>reduction</strong> from the <strong>maximum independent set</strong>, using the idea from <a href="https://cstheory.stackexchange.com/questions/6297/maximizing-sum-edge-weights/6326#6326">Neal Young </a>. Hope it is correct or at least helpful.</p>

<p>Given an undirected graph <span class="math-container">$G=(V, E)$</span>, let <span class="math-container">$A$</span> be the set of the edges. For each node <span class="math-container">$v$</span> in <span class="math-container">$V$</span>, create <span class="math-container">$d_v-1$</span> elements say <span class="math-container">$\{b_v^{1},...,b_v^{d_v-1}\}$</span> where <span class="math-container">$d_v$</span> is the degree of <span class="math-container">$v$</span>. Put all the created elements in <span class="math-container">$B$</span>. For each node <span class="math-container">$v$</span>, creat a subset <span class="math-container">$S_v$</span> of <span class="math-container">$A\cup B$</span> as the edges adjacent to <span class="math-container">$v$</span> plus the elements <span class="math-container">$\{b_v^{1},...,b_v^{d_v-1}\}$</span>.</p>

<p>Each subset <span class="math-container">$C^{'}$</span> of <span class="math-container">$\{S_v\}_{v\in V}$</span> corresponds a subset of nodes in <span class="math-container">$G$</span>.</p>

<p><span class="math-container">$\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right|$</span> is the number of edges covered by these nodes.</p>

<p><span class="math-container">$\left|\left(\bigcup\limits_{c \in C'} c\right) \cap B\right|$</span> is <span class="math-container">$\sum_{v \in C^{'}}(d_v-1)$</span>.</p>

<p>Suppose we have a <span class="math-container">$C^{'}$</span> with <span class="math-container">$\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right|-\left|\left(\bigcup\limits_{c \in C'} c\right) \cap B\right|\geq k$</span>.</p>

<p>Without loss generality, we assume no two nodes <span class="math-container">$u$</span> and <span class="math-container">$v$</span> in <span class="math-container">$C^{'}$</span> are adjacent. For otherwise, we can remove namely <span class="math-container">$v$</span> from <span class="math-container">$C^{'}$</span>, then <span class="math-container">$\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right|$</span> will decrease by at most <span class="math-container">$d_v-1$</span> while <span class="math-container">$\left|\left(\bigcup\limits_{c \in C'} c\right) \cap B\right|$</span> will decrease by <span class="math-container">$d_v-1$</span>.</p>

<p>When no two nodes <span class="math-container">$u$</span> and <span class="math-container">$v$</span> in <span class="math-container">$C^{'}$</span> are adjacent, <span class="math-container">$\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right|$</span> is <span class="math-container">$\sum_{v \in C^{'}}d_v$</span>, and therefore <span class="math-container">$\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right|-\left|\left(\bigcup\limits_{c \in C'} c\right) \cap B\right|=|C^{'}|$</span>. So you have an independent set with size at least <span class="math-container">$k$</span>.</p>

CC BY-SA 4.0
2019-06-07T02:26:35.720Z
2019-06-07T02:26:35.720Z
Arthur
<p>I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem:</p>

<p><strong>Input</strong>: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup B=U$. We're also given a collection $C$ of $k$ sets $S_1,S_2,\ldots,S_k$ where $S_i \subseteq U$ for all $i=1\ldots k$. The sets $S_1,S_2,\ldots,S_k$ may or may not be disjoint, and the union of all $S_i$ may or may not equal the universe.</p>

<p><strong>Solution form</strong>: A collection $C' \subseteq C$.</p>

<p><strong>Objective function</strong>: Maximize $\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right| - \left|\left(\bigcup\limits_{c \in C'} c\right) \cap B\right|$</p>

<p>In English, the objective function rewards solutions that cover a large number of elements in $A$ and penalizes those that cover a large number of elements in $B$. The best solution would be one that covers $A$ fully and does not cover $B$ at all. The worst solution covers $B$ fully and does not cover $A$ at all. The cardinality of $C'$ is not important.</p>

<p>Example: Universe $U=\left\{1,2,3,4,5\right\}$. Susbsets $A=\left\{1,3,4,5\right\}$ and $B=\left\{2\right\}$. Sets $S_1=\left\{1,2,3,5\right\}$, $S_2=\left\{1,4\right\}$ and $S_3=\left\{2,5\right\}$. Here the best solution is to take $S_1$ and $S_2$, which gives a measure value of $3$.</p>

<p>It's relatively trivial to adapt the classical greedy heuristic to get an approximate solution. <strong>My questions are</strong> 1) is this problem studied in any literature, and 2) do you think it would be possible to prove an approximation ratio for the greedy heuristic on it?</p>

<p>I had a look at <a href="http://www.csc.kth.se/~viggo/wwwcompendium/" rel="nofollow noreferrer">A compendium of NP optimization problems</a> and questions like <a href="https://cstheory.stackexchange.com/questions/4/what-is-the-following-variation-on-set-cover-known-as">this one</a>, but haven't been able to find anything similar yet.</p>

CC BY-SA 3.0
2014-10-07T20:49:56.110Z
I think, in general, it is NP-hard to approximate this by any multiplicative factor, because it is NP-hard to decide whether there is a solution that makes the objective function value positive.  To see why, reduce (standard) set-cover to it.  Given a set-cover instance and an integer k, put all the elements into A.  Then create k-1 new elements, put them in B, and add them all to all the sets from the original set-cover instance.  The resulting instance of your problem will have a solution with value >= 1 iff the original set-cover instance had a set-cover with value k or more.
Neal Young
CC BY-SA 3.0
2014-10-08T08:20:35.700Z
Thanks for your comment...it was very helpful! I've added my own answer below which you might be interested in.
sammy34
<cc.complexity-theory><np-hardness><approximation-algorithms><set-cover><set-theory>
Variation on partial Set Cover with penalties
sammy34
# Variation on partial Set Cover with penalties

(Asked by: username_0 on 2014-10-07)

I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem:

**Input**: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup B=U$. We're also given a collection $C$ of $k$ sets $S\_1,S\_2,\ldots,S\_k$ where $S\_i \subseteq U$ for all $i=1\ldots k$. The sets $S\_1,S\_2,\ldots,S\_k$ may or may not be disjoint, and the union of all $S\_i$ may or may not equal the universe.

**Solution form**: A collection $C' \subseteq C$.

**Objective function**: Maximize $\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap A\right| - \left|\left(\bigcup\limits\_{c \in C'} c\right) \cap B\right|$

In English, the objective function rewards solutions that cover a large number of elements in $A$ and penalizes those that cover a large number of elements in $B$. The best solution would be one that covers $A$ fully and does not cover $B$ at all. The worst solution covers $B$ fully and does not cover $A$ at all. The cardinality of $C'$ is not important.

Example: Universe $U=\left\{1,2,3,4,5\right\}$. Susbsets $A=\left\{1,3,4,5\right\}$ and $B=\left\{2\right\}$. Sets $S\_1=\left\{1,2,3,5\right\}$, $S\_2=\left\{1,4\right\}$ and $S\_3=\left\{2,5\right\}$. Here the best solution is to take $S\_1$ and $S\_2$, which gives a measure value of $3$.

It's relatively trivial to adapt the classical greedy heuristic to get an approximate solution. **My questions are** 1) is this problem studied in any literature, and 2) do you think it would be possible to prove an approximation ratio for the greedy heuristic on it?

I had a look at [A compendium of NP optimization problems](http://www.csc.kth.se/~viggo/wwwcompendium/) and questions like [this one](https://cstheory.stackexchange.com/questions/4/what-is-the-following-variation-on-set-cover-known-as), but haven't been able to find anything similar yet.

**Tags:** cc.complexity-theory, np-hardness, approximation-algorithms, set-cover, set-theory
> **Comments:**
> **username_1**: I think, in general, it is NP-hard to approximate this by any multiplicative factor, because it is NP-hard to decide whether there is a solution that makes the objective function value positive.  To see why, reduce (standard) set-cover to it.  Given a set-cover instance and an integer k, put all the elements into A.  Then create k-1 new elements, put them in B, and add them all to all the sets from the original set-cover instance.  The resulting instance of your problem will have a solution with value >= 1 iff the original set-cover instance had a set-cover with value k or more.  
> **username_0**: Thanks for your comment...it was very helpful! I've added my own answer below which you might be interested in.  

---

## 3 answers

### Answer by username_2 on 2014-10-07. Score: 5

This answers question (2):

The greedy heuristic for Set Cover / Maximum Coverage always picks the set which contains the maximal number of uncovered elements.

Assuming your modification for the heuristic is picking the set which greedily increases the solution profit, you might end up in a lousy approximation ratio.

Consider the following example:
$$A = \{a\_1,a\_2,\ldots a\_{k}\}, B=\{b\_1,b\_2,\ldots b\_k\}$$
$$C = \{C\_1\} \cup C\_2$$
$$C\_1= A\cup B \setminus\{b\_1\}$$
$$ C\_2 = \{\{a\_{i},b\_1\}|i\in[k]\}$$

The greedy heuristic will output $C'=\{C\_1\}$, so the profit is $1$, while the optimal solution is $C\_2$ which gives profit $k-1$.

> **Comments:**
> **username_0**: Thanks for your answer...very useful to have a concrete example! I've added my own answer below which you might be interested in.  
> **username_2**: @sammy34 - read it (and upvoted :) ). I've found this problem interesting and I'll take a look at the papers in the answer. btw, There's nothing wrong in answering your own question.  

---

### Answer by username_0 on 2014-10-08. Score: 2

Sorry for answering my own question, but I found the answer quite clearly.

To question 1: It turns out that this problem [has been studied by Pauli Miettinen](http://www.sciencedirect.com/science/article/pii/S0020019008001592) not too long ago. The intuitive name given to it is "The Positive-Negative Partial Set Cover problem".

To question 2: Although the adapted trivial heuristic (each time picking the set which greedily increases the solution profit) is not discussed in the paper, Miettinen (in Corollary 3) tells us the following:

*There exists a polynomial-time approximation algorithm for the Positive-Negative Partial Set Cover problem that achieves an approximation factor of $2 \sqrt{\left(m + \pi\right) \log \pi}$, where $m$ and $\pi$ relate to the related approximation of the Red-Blue Set Cover problem (see the paper).*

The polynomial-time algorithm he references is that [given in Peleg](http://www.sciencedirect.com/science/article/pii/S1570866706000189), which I'm now off to try to understand :).

I thank you all for your contributions and comments!!

**UPDATE**

So, the plot thickens. Neal Young kindly and correctly pointed out that Miettinen's objective function is different to mine (see comments). Verbosely...

Understanding my original $A$ set to be the elements we generally *do* want covered, and my original $B$ set to be the elements we generally *don't* want covered, we understand *my* objective function as maximizing (same as in my initial post)

$\left| \left(\bigcup\limits\_{c \in C'} c \right) \cap A \right| - \left| \left(\bigcup\limits\_{c \in C'} c \right) \cap B \right|$.

This is equivalent to *minimizing* (Miettinen minimizes cost rather than maximizing profit)

$\left| \left(\bigcup\limits\_{c \in C'} c \right) \cap B \right| - \left| \left(\bigcup\limits\_{c \in C'} c \right) \cap A \right|$.

With a bit of manipulation

$\left| \left(\bigcup\limits\_{c \in C'} c \right) \cap B \right| - \left| \left(\bigcup\limits\_{c \in C'} c \right) \cap A \right| + \left( \left| A \setminus \left(\bigcup\limits\_{c \in C'} c \right) \right| - \left| A \setminus \left(\bigcup\limits\_{c \in C'} c \right) \right| \right)$

$\Leftrightarrow \left( \left| A \setminus \left(\bigcup\limits\_{c \in C'} c \right) \right| + \left| \left(\bigcup\limits\_{c \in C'} c \right) \cap B \right| \right) - \left| A \right|$

we see that (the minimization form of) my objective function *plus* $\left|A\right|$ is equivalent to Miettinen's objective function (in parentheses).

Miettinen's objective function is not exactly what I'm looking for. Actually, all this has made me realise that even my objective function isn't exactly in line with my objective (oh dear)! I'm going to take a step back, reformulate, and ask a separate question if required. Again, thank you all for your help.

> **Comments:**
> **username_1**: Taking a look at Miettinen's paper, isn't the objective function different than in your problem?  His objective is yours, plus |B|.  That is, his objective counts the number of covered elements in A, plus the number of uncovered elements in B.  His objective is equivalent to yours w.r.t. exact optimization, but not w.r.t. multiplicative-factor approximation.  (His is easier to approximate.)  
> **username_0**: Thank you so much for picking me up on this. I've updated my answer.  

---

### Answer by username_3 on 2019-06-07. Score: 0

I am trying to give a **reduction** from the **maximum independent set**, using the idea from [Neal Young](https://cstheory.stackexchange.com/questions/6297/maximizing-sum-edge-weights/6326#6326) . Hope it is correct or at least helpful.

Given an undirected graph $G=(V, E)$, let $A$ be the set of the edges. For each node $v$ in $V$, create $d\_v-1$ elements say $\{b\_v^{1},...,b\_v^{d\_v-1}\}$ where $d\_v$ is the degree of $v$. Put all the created elements in $B$. For each node $v$, creat a subset $S\_v$ of $A\cup B$ as the edges adjacent to $v$ plus the elements $\{b\_v^{1},...,b\_v^{d\_v-1}\}$.

Each subset $C^{'}$ of $\{S\_v\}\_{v\in V}$ corresponds a subset of nodes in $G$.

$\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap A\right|$ is the number of edges covered by these nodes.

$\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap B\right|$ is $\sum\_{v \in C^{'}}(d\_v-1)$.

Suppose we have a $C^{'}$ with $\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap A\right|-\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap B\right|\geq k$.

Without loss generality, we assume no two nodes $u$ and $v$ in $C^{'}$ are adjacent. For otherwise, we can remove namely $v$ from $C^{'}$, then $\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap A\right|$ will decrease by at most $d\_v-1$ while $\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap B\right|$ will decrease by $d\_v-1$.

When no two nodes $u$ and $v$ in $C^{'}$ are adjacent, $\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap A\right|$ is $\sum\_{v \in C^{'}}d\_v$, and therefore $\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap A\right|-\left|\left(\bigcup\limits\_{c \in C'} c\right) \cap B\right|=|C^{'}|$. So you have an independent set with size at least $k$.


---

