# expected number of sets generated by greedy set cover ?

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 ?

• 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 Sep 9 '12 at 19:17
• 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 Sep 9 '12 at 19:26
• That s exactly what I want. But how did you get the cardinality of the largest set ? [is it a known fact ? ] – AJed Sep 10 '12 at 19:54
• 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 Sep 10 '12 at 22:46
• Maybe it should be an answer since it addresses the OP's point – Suresh Venkat Sep 11 '12 at 3:00

• 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 or Chvatal).

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

• very interesting. but this is not the standard greedy set cover algorithm - (or there is a trick in there ?) – AJed Nov 3 '12 at 15:23
• The argument does apply to the standard greedy set-cover algorithm. I edited the proof to try to make that more clear. – Neal Young Nov 3 '12 at 17:33
• I get your point. – AJed Nov 3 '12 at 17:34
• 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 Nov 25 '12 at 19:50
• 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 Nov 25 '12 at 21:44