Analyzing Weighted Set-Cover variant

Question

A standard greedy algorithm for solving the weighted set-cover problem can be proven to be a $\log(n)$ approximation. I have a variant of weighted set cover, and I came up with a greedy algorithm for solving it. I'm trying to figure out what kind of approximation said algorithm is.

The standard weighted set-cover problem is: given a universe $U$ and a family of sets $\mathcal{F} = \{S_1, S_2, \dots, S_m\}$ where $S_i$ has cost $C_i$ we want:

$\min_{I\subseteq [m]}\sum_{i\in I}C_i$ $\mathrm{s.t.} \bigcup_{i\in I}S_i = U$

The traditional greedy algorithm for solving it goes something like this:

1. Let $X \leftarrow U, I = \emptyset$
2. Repeat until $X = \emptyset$
   Pick $i$ s.t. $\frac{|X\cap S_i|}{C_i}$ is maximized
   $I\leftarrow I\cup \{i\}, X\leftarrow X\setminus S_i$

This algorithm can be proven to be an $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} = O(\log(n))$ approximation.

Now for my variations to the problem:

1. I am not trying to cover the entire universe $U$, instead I have some desired elements $D\subseteq U$ that I'm trying to cover.
2. I have another set of elements of $U$ that I do not want to cover. My algorithm needs to actively avoid them, let's call this set $A\subset U$. By definition $D\cap A = \emptyset$.
3. The cost of selecting the set $S_i$ is not fixed or given a-priori. Instead, it is a function of the already selected sets. For instance, assuming $\mathcal{C} \subset \mathcal{F}$ is the set of already selected sets, $C_i$ could be something like this: $C_i = k_1|S_i\cap(A\setminus\mathcal{C})| - k_2|S_i\cap(D\setminus\mathcal{C})| - |S_i|$
   where $k_1$ and $k_2$ are constants. This is basically saying: $k_1$ times how may of the sets we want to avoid would $S_i$ add, minus $k_2$ times how many yet uncovered sets is would cover, minus $S_i$'s size.

The algorithm I came up with is very similar to the greedy solution to weighted set-cover, but having the costs vary is making it very difficult for me to analyze it.

FWIW, this is the algorithm:

1. Let $X\leftarrow D,\ \mathcal{X} = \mathcal{F},\ \mathcal{C} = \emptyset$
2. Repeat until $X = \emptyset$ or $\mathcal{X} = \emptyset$ Pick $i$ s.t. $C_i$ (from above) is minimized
   $\mathcal{X}\leftarrow\mathcal{X}\setminus \{S_i\},\ X\leftarrow X\setminus S_i,\ \mathcal{C}\leftarrow\mathcal{C}\cup\{S_i\}$

Any ideas about how to analyze this to see what kind of approximation it is?

Answer 1

Rather than focusing on the greedy algorithm, you could also look at the LP formulation. Let's take the specific cost function that you provide. Notice that each element of A is charged $k_1$ if it appears at all in the cover, and each element of $D$ is charged $-k_2$ if it appears in the cover.

Given that, and the fact that you have to cover all elements in $D$, it means that you're going to incur a fixed cost of $-k_2 |D|$ regardless of what else you do, so you might as well ignore it for the purpose of finding the solution.

This leaves the elements in $A$. Set up an LP where there's an indicator variable $x_S$ for each set $S$ as usual, and a variable $y_a$ for each element $a \in A$. Now your cost function can be written as $$ C = k_1\sum y_a - \sum |S| x_S $$ subject to the constraints $$\forall S, 0 \le x_S \le 1$$ $$ \forall a, S \text{ contains } a, x_S \le y_a$$ Notice that the second constraint ensures that you have to charge a cost to $y_a$ if you pick any of the sets that contain it. The minimization of $C$ ensures that you'll always pick $y_a = x_S$ for some $S$.

At this point you have either an LP-rounding problem to solve (and you can look at standard ways of solving set-cover-ish LPs via rounding), or you can think of the primal-dual formulation, which essentially leads to greedy in any case.

Answer 2

May be the paper Robert D. Carr et aL., "On the red-blue set cover problem", SODA 2000 could help. From the abstract: "Given a finite set of red elements $R$, a finite set of blue elements $B$ and a family $S\subseteq 2^{RB}$, the red-blue set cover problem is to find a subfamily $\cal C$ which covers all blue elements, but which covers the minimum possible number of red elements." They give approximation algorithms for it.