expected number of sets generated by greedy set cover ?

Question

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 ?

Answer 1

• 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