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 ?
-
$\begingroup$ 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$? $\endgroup$– Sasho NikolovSep 9, 2012 at 19:17
-
4$\begingroup$ 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. $\endgroup$– Sasho NikolovSep 9, 2012 at 19:26
-
$\begingroup$ That s exactly what I want. But how did you get the cardinality of the largest set ? [is it a known fact ? ] $\endgroup$– AJedSep 10, 2012 at 19:54
-
3$\begingroup$ 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. $\endgroup$– Sasho NikolovSep 10, 2012 at 22:46
-
$\begingroup$ Maybe it should be an answer since it addresses the OP's point $\endgroup$– Suresh VenkatSep 11, 2012 at 3:00
1 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 or Chvatal).
Define the fractional cover $X$ in two stages.
Give each set $s$ weight $X_s = 2/pk$.
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
$n e^{-2sp} \rightarrow \infty$, and
$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
-
$\begingroup$ very interesting. but this is not the standard greedy set cover algorithm - (or there is a trick in there ?) $\endgroup$– AJedNov 3, 2012 at 15:23
-
1$\begingroup$ The argument does apply to the standard greedy set-cover algorithm. I edited the proof to try to make that more clear. $\endgroup$ Nov 3, 2012 at 17:33
-
-
$\begingroup$ 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 ? $\endgroup$– AJedNov 25, 2012 at 19:50
-
$\begingroup$ 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. $\endgroup$ Nov 25, 2012 at 21:44