• CONTEST ALERT - Experience the power of DDR5 memory with Kingston Click for details

Need help with Greedy Technique Problem

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?
 
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.
 
OP
Harsh Pranami

Harsh Pranami

Padawan
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?
 
> 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.
 
Top Bottom