I am trying to understand the problem statement and the approximation algorithm for the Unique Coverage Problem from these notes. I have refined the question based on the comments provided. Thanks to D.W for pointing out Exact Cover problem.
Given a universe $U = \{ e_1, e_2, \dots, e_n\}$ of n elements and given a collection $\mathcal{S} = \{S_1, S_2, \dots, S_m\}$ of subsets of $U$ such that $\bigcup\limits_{S{_i}\in\mathcal{S}} S_i$, is equal to $U$.
Exact cover is a decisional problem of finding if there exists a sub-collection of subsets $\mathcal{S^{'}} \subseteq \mathcal{S}$, which can cover the Universe $U$ and each element $e \in U$ is contained exactly in one subset $s \in \mathcal{S^{'}}$.
Unique coverage problem is to find a sub-collection $\mathcal{S}^{'} \subseteq \mathcal{S}$, such that, pairwise intersection of $s \in \mathcal{S^{'}} = \phi$ and cardinality of $\bigcup\limits_{S{_i}\in\mathcal{S}} S_i$ is maximum.
My questions are,
- Are the definitions written above correct?
- Is the Unique Cover Problem a computational version of Exact Cover? (Exact cover requires universe $U$ to be completely covered, while Unique cover problem tries to maximize the cover of universe $U$).
From this video,I got the following example and answer for this example as 6, at duration 11:46.
$U = \{1,2,3,4,5,6,7,8\}$
$S_1 = \{1,2,5 \}$; $S_3 = \{1,5,6,7\}$
$S_2 = \{1,3,8 \}$; $S_4 = \{2,4,6,8\}$
It is also mentioned in the video that the answer is 6 and its when unique cover is $\{S_3, S_4\}$, but $\{S_3 \cap S_4\} = \{6\} \neq \phi$.
- Isn't the answer to above example should be either $S_3$ or $S_4$, whose cardinality is 4?
The algorithm given in the notes is as following:
- 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}$
Applying the algorithm to above example, we get:
$class_1: \{3,4,7\}$; $class_2: \{2,5,6,8\}$; $class_3: \{1\}$
As cardinality of class 2 is maximum among others, we pick $i = 2$.
What does the algorithm mean to say,
- Choose any set with probability $\frac1{2^i} = \frac1{4}$?
(the probability of what?)
- Choose any set with probability $\frac1{2^i} = \frac1{4}$?
Can anyone explain how this algorithm will give a $\mathcal{O}(log \text{ }n)$ approximation of optimal solution?