Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.