I was reading about the $\mathcal{O}(\frac{1}{\log n})$ approximation algorithm for the Unique Coverage Problem from these notes.

The gist of the algorithm is as follows:

  • Partition the elements into $\log n$ classes according to their degrees, i.e., the number of sets that cover the element. So class $i$ contains all the elements which are covered with at least $2^i$ and at most $2^{i+1}$ sets.
  • Let $i$ be the class of the maximum cardinality.
  • Choose any set with probability $\frac1{2^i}$

Then in Lemma 3, they go on to show that

Lemma 3: The expected number of the elements uniquely covered from class $i$ is $\frac{1}{e^2}$ fraction of the element in class $i$.

I was able to follow the algorithm till here but I am completely stumped as to how they arrived at the statement immediately following lemma 3

Therefore, the total profit of uniquely covered elements is at least $\frac{1}{e^2 \log n} \times \text{opt}$

How did they arrive to this conclusion? They didn't even show what the upper bound is for this maximization algorithm. What am I overlooking?

It is trivial to prove that the expected number of unique elements covered by the algorithms is $\frac{n}{e^2}$ since it directly follows Lemma 3 but that is about all that I am able to observe :/


Suppose there are $m$ elements and $n$ sets (this is the meaning of your parameter $n$). The algorithm divides the set of elements into $\log n$ classes, so one of these classes, say class $i$, contains at least $m/\log n$ elements. Lemma 3 shows that if you pick each set with probability $1/2^i$, then in expectation you uniquely cover a $1/e^2$ fraction of the elements in class $i$. Thus, you uniquely cover at least $m/(e^2\log n)$ elements in expectation. On the other hand, the optimal cover uniquely covers at most $m$ elements. Thus the approximation ratio of this algorithm is at least $1/(e^2\log n)$.

| cite | improve this answer | |
  • $\begingroup$ But isn't this analysis lose? I mean, if we expect to cover $\frac{1}{e^2}$ elements from each class, if we take this sum over all the classes, by linearity of expectation, don't we expect to cover $\frac{m}{e^2}$ number of elements? This will give us a constant $\frac{1}{e^2}$ approximation scheme. $\endgroup$ – Banach Tarski Sep 24 '16 at 18:40
  • $\begingroup$ Not quite. Don't forget that we have to cover elements uniquely. $\endgroup$ – Yuval Filmus Sep 24 '16 at 18:42
  • $\begingroup$ But the lemma says "The expected number of the elements uniquely covered from class $i$ is $\frac{1}{e^2}$ fraction of the element in class $i$" So from each class we expect to uniquely cover $\frac{1}{e^2}$ of the elements right? $\endgroup$ – Banach Tarski Sep 24 '16 at 18:45
  • $\begingroup$ Yes, but you will also cover elements from other classes. Take a couple of hours to think about it. $\endgroup$ – Yuval Filmus Sep 24 '16 at 18:47
  • $\begingroup$ Oh I see so Lemma 3 was specifically for class $i$ with the maximum cardinality and wasn't used as an index variable since the inequalities won't carry through for the other classes. Did I get it right? $\endgroup$ – Banach Tarski Sep 24 '16 at 18:59

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.