1
$\begingroup$

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,

  1. Are the definitions written above correct?
  2. 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$.

  1. 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$.

  1. What does the algorithm mean to say,

    • Choose any set with probability $\frac1{2^i} = \frac1{4}$?
      (the probability of what?)
  2. Can anyone explain how this algorithm will give a $\mathcal{O}(log \text{ }n)$ approximation of optimal solution?

$\endgroup$
  • 2
    $\begingroup$ What do you mean by walking you through? Could yo narrow your question and specify explicitly where you got stuck? The question should be self-contained, $\endgroup$ – Evil Sep 27 '16 at 14:38
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Exact_cover $\endgroup$ – D.W. Sep 27 '16 at 14:50
  • 3
    $\begingroup$ Indeed, can you clarify what is confusing? To me, it looks like the example fits the problem definition (but I think there's a typo in the definition: the union of $S_i$'s should probably equal $U$). Also, what algorithm are you referring to at the end, and what is claimed to be $O(\log n)$ (strictly speaking, it doesn't mean anything to say "an algorithm is $O(\log n)$). $\endgroup$ – Juho Sep 27 '16 at 14:51
  • $\begingroup$ @D.W. thank you very much for pointing out Exact Cover problem. @ Evil and @ Juho , I have refined the question as per your suggestions. I have added the algorithm into the question and tried to make the question self contained. Thank you all once again. $\endgroup$ – user0x0 Oct 3 '16 at 13:21
2
$\begingroup$

Let's go over your questions one by one:

(1) Your definition of Unique cover is wrong. Given a set system $\mathcal{S}$, the goal is to find a subset $\mathcal{S}' \subseteq \mathcal{S}$ which uniquely covers the most elements. The subset $\mathcal{S}'$ uniquely covers an element $x$ if $x$ belongs to exactly one set in $\mathcal{S}'$.

(2) Exact cover is a decision problem, whereas Unique cover is an optimization problem. The decision version of Unique cover goes as follows:

Given a set system and an integer $k$, is there a subset of the set system which uniquely covers at least $k$ elements?

Exact cover is a special case of the decision version of Unique cover.

(3) The sets $S_3$ and $S_4$ together cover $6$ elements once ($1,2,4,5,7,8$). Since $6 > 4$, it is better to take both $S_3$ and $S_4$ rather than any of them individually.

(4) The probability is that of choosing any given set. I suggest you look for more material on probability theory and on randomized algorithms, and after that come back and see if it makes sense.

(5) This is explained very clearly in various lecture notes. There is no point repeating the explanation here. I suggest you learn probability theory and randomized algorithms from scratch, and then attempt to read the $O(\log n)$ analysis again. It might take a few weeks, but without catching up on the basics you have no chance of understanding anything which is even slightly advanced.

$\endgroup$

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.