2 added 1 character in body

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{2i}$$$$\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 :/

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{2i}$$

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 :/

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 :/

1

# 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{2i}$$

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 :/