A standard greedy algorithm for solving the weighted set-cover problem can be proven to be a $ln 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?

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?