Analyzing Weighted Set-Cover variant 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:


*

*Let $X \leftarrow U, I = \emptyset$

*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:


*

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

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

*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:


*

*Let $X\leftarrow D,\ \mathcal{X} = \mathcal{F},\ \mathcal{C} = \emptyset$

*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?
 A: 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. 
A: 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. 
