1
$\begingroup$

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

enter image description here

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"?

$\endgroup$
  • $\begingroup$ Do you have a question? I find it hard to tell what you are asking. I'm not sure what ``Does anyone know the "trick"?'' means -- can you edit your question to be more specific about what you are asking? Also, if you figure out the answer to your own question, instead of editing the question to add the answer into the question, we'd prefer that you answer your own question by putting the answer in the 'answer' box below. $\endgroup$ – D.W. Jun 25 '17 at 4:03
  • $\begingroup$ I'm voting to close this question since it has been resolved. $\endgroup$ – Yuval Filmus Jun 25 '17 at 4:11
  • $\begingroup$ Please post your answer as an answer, not as an extension to the question. Answering your own questions is fine and helps future users of the site who might have the same problem. $\endgroup$ – David Richerby Jun 25 '17 at 20:00
  • $\begingroup$ @YuvalFilmus But the whole point of the site is to answer questions! The fact that the answer has been posted in the wrong place doesn't alter that. $\endgroup$ – David Richerby Jun 25 '17 at 20:01
  • $\begingroup$ Done! The answer is now presented as an answer rather than a question's extension. $\endgroup$ – André Gomes Jun 25 '17 at 20:07
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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