7
$\begingroup$

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 ?

$\endgroup$
  • $\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 Nikolov Sep 9 '12 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 Nikolov Sep 9 '12 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$ – AJed Sep 10 '12 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 Nikolov Sep 10 '12 at 22:46
  • $\begingroup$ Maybe it should be an answer since it addresses the OP's point $\endgroup$ – Suresh Venkat Sep 11 '12 at 3:00
5
$\begingroup$
  • 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

$\endgroup$
  • $\begingroup$ very interesting. but this is not the standard greedy set cover algorithm - (or there is a trick in there ?) $\endgroup$ – AJed Nov 3 '12 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$ – Neal Young Nov 3 '12 at 17:33
  • $\begingroup$ I get your point. $\endgroup$ – AJed Nov 3 '12 at 17:34
  • $\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$ – AJed Nov 25 '12 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$ – Neal Young Nov 25 '12 at 21:44

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.