I am looking for the answer to the exercise 1-6 in "The Algorithm Design Manual" book. it is stated as follows:
1-6. The set cover problem is as follows: given a set of subsets $S_1,\dots,S_m$ of the universal set $U = \{1,\dots,n\}$, find the smallest subset of $T \subset S$ subsets such that $\cup_{t_i \in T} t_i = U$. For example, there are the following subsets, $S_1 = \{1,3,5\}$, $S_2 = \{2,4\}$, $S_3 = \{1,4\}$, and $S_4 = \{2,5\}$. The set cover would then be $S_1$ and $S_2$.
Find a counterexample for the following algorithm: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered.
My answer is as follows:
$S = \{\{1, 2\}, \{3, 4\}, \{2, 5\}, \{5\}\}$, $U=\{1,2,3,4,5\}$.
The algorithm will use the following sets: $\{\{1, 2\}, \{3, 4\}, \{2, 5\}\}$, while {{1, 2}, {3, 4}, {5}}$. would be more minimal.
Do you think its correct? I assume here that algorithm minimizes number of uncovered elements in each iteration and not the entire size of set to choose – that's why it might choose $\{2,5\}$ instead of $\{5\}$.
I have found this answer online:
One counter-example consists of a series of subsets that increases in size exponentially, plus 2 additional subsets that each cover half of the elements. Example:
$S_1 = \{1,2\}$
$S_2 = \{3,4,5,6\}$
$S_3 = \{7,8,9,10,11,12,13,14,15,16\}$
$S_4 = \{1,2,3,4,5,6,7,8\}$
$ S_5 = \{9,10,11,12,13,14,15,16\}$
The greedy algorithm will choose $S_3,S_2,S_1$, while the optimal solution is simply $S_4,S_5$.
My understanding is that the algorithm would choose $S_3,S_4$ and not $S_3,S_2,S_1$, since $S_4$ has more uncovered elements than $S_2$.