Approximation Algorithm for the Unique Coverage Problem - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T16:02:37Z https://cs.stackexchange.com/feeds/question/63830 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/63830 3 Approximation Algorithm for the Unique Coverage Problem Banach Tarski https://cs.stackexchange.com/users/46799 2016-09-24T17:24:19Z 2016-09-24T18:34:38Z <p>I was reading about the $\mathcal{O}(\frac{1}{\log n})$ approximation algorithm for the Unique Coverage Problem from <a href="http://www.cs.umd.edu/~hajiagha/NetDsgn11/scribe-14-09-2011.pdf" rel="nofollow">these</a> notes.</p> <p>The gist of the algorithm is as follows:</p> <blockquote> <ul> <li>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.</li> <li>Let $i$ be the class of the maximum cardinality.</li> <li>Choose any set with probability $\frac1{2^i}$</li> </ul> </blockquote> <p>Then in Lemma 3, they go on to show that</p> <blockquote> <p><strong>Lemma 3:</strong> The expected number of the elements uniquely covered from class $i$ is $\frac{1}{e^2}$ fraction of the element in class $i$.</p> </blockquote> <p>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</p> <blockquote> <p>Therefore, the total profit of uniquely covered elements is at least $\frac{1}{e^2 \log n} \times \text{opt}$</p> </blockquote> <p>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?</p> <p>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 :/</p> https://cs.stackexchange.com/questions/63830/-/63832#63832 3 Answer by Yuval Filmus for Approximation Algorithm for the Unique Coverage Problem Yuval Filmus https://cs.stackexchange.com/users/683 2016-09-24T18:22:02Z 2016-09-24T18:22:02Z <p>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)$.</p>