4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Neal Young Oct 7 '14 at 20:49
  • $\begingroup$ Thanks for your comment...it was very helpful! I've added my own answer below which you might be interested in. $\endgroup$ – sammy34 Oct 8 '14 at 8:20
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for your answer...very useful to have a concrete example! I've added my own answer below which you might be interested in. $\endgroup$ – sammy34 Oct 8 '14 at 8:23
  • $\begingroup$ @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. $\endgroup$ – R B Oct 8 '14 at 8:34
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Neal Young Oct 8 '14 at 16:21
  • $\begingroup$ Thank you so much for picking me up on this. I've updated my answer. $\endgroup$ – sammy34 Oct 9 '14 at 8:38
0
$\begingroup$

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

$\endgroup$

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.