Variation on partial Set Cover with penalties

Question

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 and questions like this one, but haven't been able to find anything similar yet.

Answer 1

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$.

Answer 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 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, 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.

Answer 3

I am trying to give a reduction from the maximum independent set, using the idea from Neal Young . 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$.