<ul>
<li><p>Given that a cover exists, greedy will return a cover of expected size $O(p^{-1}\log n)$.</p></li>
<li><p>As long as $k$ is not too large, with high probability every cover has size $\Omega(p^{-1}\log n)$ </p></li>
</ul>

<p>This implies that (for $k$ not too large) greedy gives an $O(1)$-approximation with probability $1-\delta$, for any constant $\delta&gt;0$.</p>

<p>Here is the upper bound, followed by the lower bound.  </p>

<h3>Upper bound</h3>

<p><em>Conditioning on the event that there exists a set cover,
the greedy set-cover algorithm returns a set cover with expected size
$O(p^{-1}\log n)$.</em></p>

<p><strong>Proof of upper bound.</strong>
Condition on the event that a set cover exists.</p>

<p>Assume without loss of generality that $k\ge (12/p)\ln(n)$
(otherwise, since greedy chooses at most $k$ sets, we are done).</p>

<p>We prove that there is a <em>fractional</em> set cover $X$ of expected size at most
$$\frac{2}{p} + n\exp(-pk/12).$$
By the assumption on $k$ this is $$O(1/p).$$</p>

<p>The upper bound will follow, because
(as is well-known) greedy returns a cover of size $O(\log n)$ 
times the size of any fractional set cover (and so, here, $O(p^{-1}\log n)$)
(see <a href="http://greedyalgs.info/blog/johnson-lovasz-derivation/" rel="nofollow">here</a> or <a href="http://scholar.google.com/scholar?cluster=16388093127208652632&amp;hl=en&amp;as_sdt=0,5" rel="nofollow">Chvatal</a>).</p>

<p>Define the fractional cover $X$ in two stages.</p>

<ol>
<li><p>Give each set $s$ weight $X_s = 2/pk$.</p></li>
<li><p>For each element $e$ such that $\sum_{e\in s} X_s &lt; 1$,
choose any set $s$ containing $e$ and raise $X_s$ enough to fully cover $e$.</p></li>
</ol>

<p>This clearly gives a fractional set cover.  (Step 2 is well defined,
because we are conditioning on the event that there is a set cover,
that is, that each element is in some set.)</p>

<p>To finish we bound the expected total weight of $X$, that is, $\sum_s X_s$.</p>

<p>Stage 1 contributes exactly $k 2/pk = 2/p$ to the total weight.</p>

<p>Stage 2 contributes, in expectation, at most $n\exp(-pk/12)$,
because each of the $n$ elements has probability at most
$\exp(-pk/12)$ of being covered with weight less than 1
by stage 1. </p>

<p>(To verify this, fix any element.
The element is left insufficiently covered 
iff it is contained in fewer than $kp/2$ sets.
The expected number of sets covering the element
is $kp$, so by a standard Chernoff bound the 
probability that the number falls below $kp/2$
is at most $$\exp(-(1/2)^2 k p/3) = \exp(-kp/12).$$
This ignores the conditioning, but the conditioning
only decreases the chance that the element is contained
in fewer than $kp/2$ sets.)
QED</p>

<p>As an aside, note that if $k$ is large enough, then greedy will almost certainly return a cover of constant size.  (E.g. if $k$ is $2n2^n$ and $p=1/2$, then won't all possible subsets be present with high probability? And in that case greedy will return just one set of course.)</p>

<h3>Lower bound</h3>

<p><em>Assuming  $p\le 1/2$, $k\le \exp(n^{1-\epsilon})$ for some $\epsilon\in [0,1/2]$,
and $s = \min((\epsilon/4p)\ln n, n^{\epsilon/2})$,
then the probability that there exists a set cover of size $s$ or less is $o(1)$.</em></p>

<p>Of course this implies that greedy does not return a set cover of size less than $s$.</p>

<p>The proof is probabilistic, using direct calculation and the naive union bound.
Hopefully there are no mistakes in the calculations.</p>

<p><strong>Proof.</strong>
Fix $p$, $k$, $s$, $\epsilon$ as above.</p>

<p>The number of ways of choosing $s$ sets from the $k$ sets available 
is ${k\choose s}$.</p>

<p>For any fixed collection of $s$ sets, the chance that it covers all
$n$ elements is $(1-(1-p)^s)^n$.</p>

<p>Combining these two observations, the expected number of size-$s$ covers among the $k$ sets is
$${k\choose s} (1-(1-p)^s)^n 
~\le~ k^s \exp(-n(1-p)^s) 
~\le~ \exp\big(s\ln(k) - n e^{-2sp}\big).$$</p>

<p>To complete the proof, one shows that the right-hand side above is $o(1)$
(under the assumptions on $k$ and $s$).</p>

<p>To do that, it suffices to show that </p>

<ol>
<li><p>$n e^{-2sp} \rightarrow \infty$, and</p></li>
<li><p>$s\ln k \le (1/e) n e^{-2sp}$.</p></li>
</ol>

<p>The first of these follows from the assumption on $s$.
The second reduces (taking logarithms) to
$$1+2ps + \ln s \le \ln(n) - \ln\ln k.$$
By the assumption on $k$ this reduces to
$$(1+2ps) + \ln s \le \epsilon \ln n.$$
This holds because the assumptions on $s$ imply that each of the two summands
on the left is at most $(\epsilon/2)\ln n$.
QED</p>

CC BY-SA 3.0
2012-11-03T15:23:18.370Z
very interesting. but this is not the standard greedy set cover algorithm -  (or there is a trick in there ?)
AJed
CC BY-SA 3.0
2012-11-03T17:33:40.463Z
The argument does apply to the standard greedy set-cover algorithm.  I edited the proof to try to make that more clear.
Neal Young
CC BY-SA 3.0
2012-11-03T17:34:48.310Z
I get your point.
AJed
CC BY-SA 3.0
2012-11-25T19:50:53.483Z
I was having a look at the pessimistic estimator method in your blog. I wonder if this upper bound of the size would work. Now given that the expected set cover size if we pick a set randomly with prob (1/$k$) is $\leq p^{-1}\ln n$. Then given the discussion about the pessimistic estimator,the greedy algorithm would perform better than the random picking of sets. Therefore, we got an upper bound of $O(p^{-1} \log n)$ without the restriction on $k$. Isn't that right as well ?
AJed
CC BY-SA 3.0
2012-11-25T21:44:15.450Z
I'm not sure what you are asking.  The *upper bound* in the answer has no restriction on $k$.  As for picking randomly, it does seem that, if, for the random set-cover instance in your example, you pick $O(p^{-1}\log n)$ sets uniformly at random, you'll be left with $O(p^{-1}\log n)$ uncovered elts, which you can cover each by a single set, to get a cover of size $O(p^{-1}\log n)$.  And greedy will do at least this well, yes.
Neal Young
CC BY-SA 3.0
2012-11-03T04:18:11.323Z
2012-11-04T16:29:25.050Z
2012-11-04T16:29:25.050Z
Neal Young
<p>I see most of the analysis for the greedy set cover analyses the approximation ratio. However, assume that each element in $T$ belong with a constant probability to one of the sets of $S$ (where $S = \{S_1, ...., S_k\}$). The question is then what is the expected number of sets generated by the greedy set cover in this case ?</p>

CC BY-SA 3.0
2012-09-09T19:17:51.780Z
i think the model is not totally clear. do you mean that the universe $T$ is fixed and $S_1, \ldots, S_k$ are independently sampled subsets of $T$, where for all $1 \leq i \leq k$ and all $e \in T$, $e \in S_i$ with probability $p$, independently from other $e$?
Sasho Nikolov
CC BY-SA 3.0
2012-09-09T19:26:30.673Z
if that is the case, here is a heuristic calculation for $p=1/2$ (should be easy to adapt to other constant $p$). Say $|T| = n$. The largest set $S_i$ is the first one picked by greedy, and has cardinality about $n(1/2 + \sqrt{\log k/n})$. When $k = n^{O(1)}$, this is very close to $n/2$. Once you remove the largest set, you're left with about $n/2$ uncovered elements. Restricting the sets to these elements, you can do the same calculation, and then you see it will take greedy $\Theta(\log n)$ sets before all elements are covered.
Sasho Nikolov
CC BY-SA 3.0
2012-09-10T19:54:37.473Z
That s exactly what I want. But how did you get the cardinality of the largest set ? [is it a known fact ? ]
AJed
CC BY-SA 3.0
2012-09-10T22:46:12.893Z
that part was a bit heuristic. the expected size of any set is $n/2$. the variance of each set size is $n/4$. the central limit theorem (CLT) suggests that each set size behaves like an independent gaussian (for large $n$), and the expected maximum of $k$ independent gaussians with expectation $n/2$ and variances $n/4$ is about $n/2 + \sqrt{n \log k}/2$. this is not a rigorous use of CLT (and I think Berry-Esseen does not suffice except for pretty small $k$), but I believe this can be fixed.
Sasho Nikolov
CC BY-SA 3.0
2012-09-11T03:00:18.593Z
Maybe it should be an answer since it addresses the OP's point
Suresh Venkat
CC BY-SA 3.0
2012-09-11T17:53:55.250Z
@SureshVenkat: actually, now that I think about it again, there is another sketchy part in my computation. it should be easy to get tight upper and lower bounds on the expected size of the largest set. but i think each next step of the algorithm is conditioned on the surviving sets not being picked so far.
Sasho Nikolov
<ds.algorithms><pr.probability><set-cover><greedy-algorithms>
expected number of sets generated by greedy set cover ?
AJed
# expected number of sets generated by greedy set cover ?

(Asked by: username_0 on 2012-09-09)

I see most of the analysis for the greedy set cover analyses the approximation ratio. However, assume that each element in $T$ belong with a constant probability to one of the sets of $S$ (where $S = \{S\_1, ...., S\_k\}$). The question is then what is the expected number of sets generated by the greedy set cover in this case ?

**Tags:** ds.algorithms, pr.probability, set-cover, greedy-algorithms
> **Comments:**
> **username_1**: i think the model is not totally clear. do you mean that the universe $T$ is fixed and $S_1, \ldots, S_k$ are independently sampled subsets of $T$, where for all $1 \leq i \leq k$ and all $e \in T$, $e \in S_i$ with probability $p$, independently from other $e$?  
> **username_1**: if that is the case, here is a heuristic calculation for $p=1/2$ (should be easy to adapt to other constant $p$). Say $|T| = n$. The largest set $S_i$ is the first one picked by greedy, and has cardinality about $n(1/2 + \sqrt{\log k/n})$. When $k = n^{O(1)}$, this is very close to $n/2$. Once you remove the largest set, you're left with about $n/2$ uncovered elements. Restricting the sets to these elements, you can do the same calculation, and then you see it will take greedy $\Theta(\log n)$ sets before all elements are covered.  
> **username_0**: That s exactly what I want. But how did you get the cardinality of the largest set ? [is it a known fact ? ]  
> **username_1**: that part was a bit heuristic. the expected size of any set is $n/2$. the variance of each set size is $n/4$. the central limit theorem (CLT) suggests that each set size behaves like an independent gaussian (for large $n$), and the expected maximum of $k$ independent gaussians with expectation $n/2$ and variances $n/4$ is about $n/2 + \sqrt{n \log k}/2$. this is not a rigorous use of CLT (and I think Berry-Esseen does not suffice except for pretty small $k$), but I believe this can be fixed.  
> **username_2**: Maybe it should be an answer since it addresses the OP's point  
> **username_1**: @SureshVenkat: actually, now that I think about it again, there is another sketchy part in my computation. it should be easy to get tight upper and lower bounds on the expected size of the largest set. but i think each next step of the algorithm is conditioned on the surviving sets not being picked so far.  

---

## 1 answers

### Answer by username_3 on 2012-11-03. Score: 5 | Accepted answer

* Given that a cover exists, greedy will return a cover of expected size $O(p^{-1}\log n)$.
* As long as $k$ is not too large, with high probability every cover has size $\Omega(p^{-1}\log n)$

This implies that (for $k$ not too large) greedy gives an $O(1)$-approximation with probability $1-\delta$, for any constant $\delta>0$.

Here is the upper bound, followed by the lower bound.

### Upper bound

*Conditioning on the event that there exists a set cover,
the greedy set-cover algorithm returns a set cover with expected size
$O(p^{-1}\log n)$.*

**Proof of upper bound.**
Condition on the event that a set cover exists.

Assume without loss of generality that $k\ge (12/p)\ln(n)$
(otherwise, since greedy chooses at most $k$ sets, we are done).

We prove that there is a *fractional* set cover $X$ of expected size at most
$$\frac{2}{p} + n\exp(-pk/12).$$
By the assumption on $k$ this is $$O(1/p).$$

The upper bound will follow, because
(as is well-known) greedy returns a cover of size $O(\log n)$
times the size of any fractional set cover (and so, here, $O(p^{-1}\log n)$)
(see [here](http://greedyalgs.info/blog/johnson-lovasz-derivation/) or [Chvatal](http://scholar.google.com/scholar?cluster=16388093127208652632&hl=en&as_sdt=0,5)).

Define the fractional cover $X$ in two stages.

1. Give each set $s$ weight $X\_s = 2/pk$.
2. For each element $e$ such that $\sum\_{e\in s} X\_s < 1$,
   choose any set $s$ containing $e$ and raise $X\_s$ enough to fully cover $e$.

This clearly gives a fractional set cover. (Step 2 is well defined,
because we are conditioning on the event that there is a set cover,
that is, that each element is in some set.)

To finish we bound the expected total weight of $X$, that is, $\sum\_s X\_s$.

Stage 1 contributes exactly $k 2/pk = 2/p$ to the total weight.

Stage 2 contributes, in expectation, at most $n\exp(-pk/12)$,
because each of the $n$ elements has probability at most
$\exp(-pk/12)$ of being covered with weight less than 1
by stage 1.

(To verify this, fix any element.
The element is left insufficiently covered
iff it is contained in fewer than $kp/2$ sets.
The expected number of sets covering the element
is $kp$, so by a standard Chernoff bound the
probability that the number falls below $kp/2$
is at most $$\exp(-(1/2)^2 k p/3) = \exp(-kp/12).$$
This ignores the conditioning, but the conditioning
only decreases the chance that the element is contained
in fewer than $kp/2$ sets.)
QED

As an aside, note that if $k$ is large enough, then greedy will almost certainly return a cover of constant size. (E.g. if $k$ is $2n2^n$ and $p=1/2$, then won't all possible subsets be present with high probability? And in that case greedy will return just one set of course.)

### Lower bound

*Assuming $p\le 1/2$, $k\le \exp(n^{1-\epsilon})$ for some $\epsilon\in [0,1/2]$,
and $s = \min((\epsilon/4p)\ln n, n^{\epsilon/2})$,
then the probability that there exists a set cover of size $s$ or less is $o(1)$.*

Of course this implies that greedy does not return a set cover of size less than $s$.

The proof is probabilistic, using direct calculation and the naive union bound.
Hopefully there are no mistakes in the calculations.

**Proof.**
Fix $p$, $k$, $s$, $\epsilon$ as above.

The number of ways of choosing $s$ sets from the $k$ sets available
is ${k\choose s}$.

For any fixed collection of $s$ sets, the chance that it covers all
$n$ elements is $(1-(1-p)^s)^n$.

Combining these two observations, the expected number of size-$s$ covers among the $k$ sets is
$${k\choose s} (1-(1-p)^s)^n
~\le~ k^s \exp(-n(1-p)^s)
~\le~ \exp\big(s\ln(k) - n e^{-2sp}\big).$$

To complete the proof, one shows that the right-hand side above is $o(1)$
(under the assumptions on $k$ and $s$).

To do that, it suffices to show that

1. $n e^{-2sp} \rightarrow \infty$, and
2. $s\ln k \le (1/e) n e^{-2sp}$.

The first of these follows from the assumption on $s$.
The second reduces (taking logarithms) to
$$1+2ps + \ln s \le \ln(n) - \ln\ln k.$$
By the assumption on $k$ this reduces to
$$(1+2ps) + \ln s \le \epsilon \ln n.$$
This holds because the assumptions on $s$ imply that each of the two summands
on the left is at most $(\epsilon/2)\ln n$.
QED

> **Comments:**
> **username_0**: very interesting. but this is not the standard greedy set cover algorithm -  (or there is a trick in there ?)  
> **username_3**: The argument does apply to the standard greedy set-cover algorithm.  I edited the proof to try to make that more clear.  
> **username_0**: I get your point.  
> **username_0**: I was having a look at the pessimistic estimator method in your blog. I wonder if this upper bound of the size would work. Now given that the expected set cover size if we pick a set randomly with prob (1/$k$) is $\leq p^{-1}\ln n$. Then given the discussion about the pessimistic estimator,the greedy algorithm would perform better than the random picking of sets. Therefore, we got an upper bound of $O(p^{-1} \log n)$ without the restriction on $k$. Isn't that right as well ?  
> **username_3**: I'm not sure what you are asking.  The *upper bound* in the answer has no restriction on $k$.  As for picking randomly, it does seem that, if, for the random set-cover instance in your example, you pick $O(p^{-1}\log n)$ sets uniformly at random, you'll be left with $O(p^{-1}\log n)$ uncovered elts, which you can cover each by a single set, to get a cover of size $O(p^{-1}\log n)$.  And greedy will do at least this well, yes.  

---

