Approximation rate for Greedy Set Cover algorithm (RESOLVED) 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}| &lt;= |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}) &lt; 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} &gt; 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} &gt; 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"?
I have figured out the answer.

The trick is not really coming from $\frac{k}{t} &gt; 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}) &lt; 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$