Approximation Algorithm for the Unique Coverage Problem

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)$.
• 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. Sep 24 '16 at 18:40
• 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? Sep 24 '16 at 18:45
• 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? Sep 24 '16 at 18:59
{"ft_lang_label":"__label__en","ft_lang_prob":0.9407261,"math_prob":0.9982573,"size":1265,"snap":"2022-05-2022-21","text_gpt3_token_len":314,"char_repetition_ratio":0.13084853,"word_repetition_ratio":0.0,"special_character_ratio":0.25296444,"punctuation_ratio":0.06827309,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9998479,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-01-19T03:05:01Z\",\"WARC-Record-ID\":\"<urn:uuid:399f819a-2166-450a-979c-e6b7105c8268>\",\"Content-Length\":\"141222\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:fc138756-50a0-42f6-822a-dd8483deda9d>\",\"WARC-Concurrent-To\":\"<urn:uuid:1bb2eae0-059b-48e3-8c2f-248e672b1250>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/63830/approximation-algorithm-for-the-unique-coverage-problem\",\"WARC-Payload-Digest\":\"sha1:WF4PPVQOQS6MDVDN2QU2IRRWEG2CTX6F\",\"WARC-Block-Digest\":\"sha1:MVBGQ722KM7WNCZ3TIY2Z5Q3Y7DOPTDJ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-05/CC-MAIN-2022-05_segments_1642320301217.83_warc_CC-MAIN-20220119003144-20220119033144-00538.warc.gz\"}"}