Approximation rate for Greedy Set Cover algorithm (RESOLVED)

Question

Set Cover: Consider a set of points X and Si a subset of X. The goal is to get the minimum number of subsets Si such as all points in X are covered. An example is shown by figure bellow. In this case, optimal solution should be OPT = {S3, S4, S5}.

Greedy Algorithm:

greedy(X, F = {S1, S2, ...}) G_OPT = {} U = X while U = empty set Pick s in F with greatest coverage in U G_OPT = G_OPT + s U = U - s return G_OPT

Goal: To find approximation rate of greedy set cover algorithm above.

What I have so far: Let t be the size of optimal soltion, $t = |OPT|$.

• At the beginning of step k + 1, the number of uncovered items in X is given by $|U_{k+1}| = |U_{k}| -$ # of newly covered items;
• By pigeonhole principle, # of newly covered items $\leq \frac{|Uk|}{t}$ and then $|U_{k+1}| \leq |U_{k}| - \frac{|U_{k}|}{t} = |Uk|(1 - \frac{1}{t})$;
• Taking the Taylor's Series of $\exp(-\frac{1}{t})$, one can easily see that $exp(-\frac{1}{t}) \geq (1 - \frac{1}{t})$;
• So, $|U_{k+1}| <= |U_{k}| \times exp(-\frac{1}{t})$;
• $|U_{0}| = |X| = n$ (none item is covered at step 0);
• Taking $|U_{1}| = n \times exp(-\frac{1}{t})$, gives $|U_{2}| = |U_{1}| \times exp(-\frac{1}{t}) = n \times exp(-\frac{2}{t})$, $|U_{3}| = |U_{2}| \times exp(-\frac{1}{t}) = n \times exp(-\frac{3}{t})$ so on and so forth. Therefore, $|U_{k}| = n \times exp(-\frac{k}{t})$;
• Lets say there is no item uncovered at k-th step. So, $|U_{k}| = 0$ and $n \times exp(-\frac{k}{t}) < 1$ (otherwise, there could be a remaining uncovered item in $U_{k}$, and this would be a contradiction of $|U_{k}| = 0)$;
• It is possible to get $\frac{k}{t} > ln(n)$ by taking log over the previous inequality.

The expected answer is $\frac{k}{t} \leq ln(n) + 1$. I have seen some lecture videos and lecture notes on the internet that give raise to the same results as I described above. However, they are all vague while getting from $\frac{k}{t} > ln(n)$ to $\frac{k}{t} \leq ln(n) + 1$.

All I can see about k, t and n is:

• $k \geq t$
• $t \leq n$

Does anyone know the "trick"?

Answer 1

I have figured out the answer.

The trick is not really coming from $\frac{k}{t} > ln(n)$ to $\frac{k}{t} \leq ln(n) + 1$ directly. Lets take 1 step back.

• Lets say there is no item uncovered at k-th step. So, $|U_{k}| = 0$ and $n \times exp(-\frac{k}{t}) < 1$ (otherwise, there could be a remaining uncovered item in $U_{k}$, and this would be a contradiction of $|U_{k}| = 0)$;

The step above can be rewritten as:

• Lets say there is no item uncovered at k-th step. So, $|U_{k}| = 0$ and we are done. We are interested in how much steps we can take before that happens. So, find the upper bound of k such as $|U_{k}| \geq 1$;
• $|U_{k}| \geq 1 \Leftrightarrow n \times exp(-\frac{k}{k}) \geq 1$. This results in $k \leq \frac{ln(n)}{t}$. So, $k = \frac{ln(n)}{t}$ is our upper bound for iterations. If $k = \frac{ln(n)}{t}$, $|U_{k}| = 1$. It's almost done. There is only 1 last item to cover and, consequently, 1 last round to run.
• Therefore, $k \leq \frac{ln(n)}{t} + 1$ in order to get $|U_{k}| = 0$. It's easy to see that $\frac{k}{t} \leq ln(n) + \frac{1}{t}$.

One can still get a cleaner solution and say $\frac{k}{t} \leq ln(n) + 1$ since $t \geq 1$.

k is the number of steps taking to get G_OPT. At each step, G_OPT increases by 1. Then, $|G\_OPT| = k$. We defined $t = |OPT|$. We end up with

Approx. rate $= \frac{|G\_OPT|}{|OPT|} \leq ln(n) + 1$