Need help with Greedy Technique Problem

[Harsh Pranami]

Here goes the question. Given a class S of sets S[SUB]i[/SUB] where 1<=i<=m. Let the size(cardinality) of a set S[SUB]i[/SUB] be j[SUB]i[/SUB]. A subset T of S, T={T[SUB]1[/SUB], T[SUB]2[/SUB], ........., T[SUB]k[/SUB]}, where T[SUB]i[/SUB]= S[SUB]r[/SUB] in S. T is a cover of S if U T[SUB]k[/SUB]= U S[SUB]i[/SUB] , 1<=i<=m. A minimum cover of S is a cover of minimum size. Consider the greedy strategy: build T by adding to T, at each stage of the iteration S[SUB]p[/SUB] from S, such that it adds largest number of elements from S, not already in T.Stop when UT[SUB]1[/SUB]= S[SUB]i[/SUB].


Can someone please explain this problem, especially the bold part?

 

[harshilsharma63]

This is what is known as the 'set cover problem'.

Suppose you have a set 'U' called the 'universe' and a set S containing subsets of U, you have to choose elements from S such that their union gives the set U.

For example:

Let U = {1,2,3,4,5,6}
and S = { {2,4,6}, {1,6,3,2}, {4,6}, {}, {5}, {6,1,4}, {4,3} }

So, you now have to choose elements form S such that their union gives back the set U.

{2,4,6}, {5}, {4,3} and {6,4,1} will do it.

What the minimum set cover problem is that you have to cover the set U using minimum number of elements from S.

The greedy approach you mentioned chooses the largest subset from S in the hope that it will include maximum number of elements of U. Though this approach looks good on paper, it may fail badly as a larger subset may not necessarily have the largest number of unvisited elements of U.

 

[Harsh Pranami]

Thanks for the reply brother. So in the question it says " such that it adds the largest no of elements from S, not already in T". So I believe the question is saying to add subset to T in each step which consists of maximum uncovered elements, not the largest subset hoping it will consist of largest number of uncovered elements. So this should be the algorithm

algo greedy_set_cover

Initialize R=U; //the set of remaining elements
while R not empty
Select set Si that contains maximum uncovered elements;
Delete elements of Si from R
end

But again there's a sub question given

>Suppose the minimum cover is defined in terms of no of elements in T summation of |Ti| for 1<=i<=k being minimum. Rewrite the algorithm and see if it always finds minimum cover.

What does this mean?

 

[harshilsharma63]

> Yeah, I got it wrong. Both the algorithms follow greedy approach but the one you have mentioned is better.

> The sub questions asks you to rewrite the set cover algorithm to minimize the sum of size of elements in set T (set T is a subset of S). In other words, it is asking to build a set cover using elements which contain as few visited elements as possible.