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
S1,…,Sm of the universal set U = {1,…,n}, find the smallest subset
of 
subsets such that 
. For example, there are the following
subsets, S1 = {1,3,5}, S2 = {2,4}, S3 = {1,4}, and S4 = {2,5} The set
cover would then be S1 and S2.
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} algorithm will use
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 – thats why it might choose {2,5} instead of {5}.
I have found this answer on internet:
One counter-example consists of a series of subsets that increase in
size exponentially, plus 2 additional subsets that each cover half of
the elements. Example:
S1 = {1,2}
S2 = {3,4,5,6}
S3 = {7,8,9,10,11,12,13,14,15,16}
S4 = {1,2,3,4,5,6,7,8}
S5 = {9,10,11,12,13,14,15,16}
The greedy algorithm will choose.
S3,S2,S1, while the optimal solution is simply S4,S5
To my understandment, algorithm would choose S3,S4 and not S3,S2,S1. S4 has more uncovered elements than S2.
