[5] The set cover problem is as follows: given a set of subsets S 1 ,...,S m of

Question

[5] 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 T ? S such that ?ti ?T ti = U . 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.

Would this be considered a counter example:

U={1,2,3,4,5,6,7}

s1 = (1,2,3,7)

s2= (3,4,5)

s3={5,6}

s4 = {2,1}

The reason for the counter example would be the algorthim would have to go through all the way to the end which would make it ineffiniant.

The Fianl set Cover would be = S1, S2,S3

If this is incorrect can you please explain and give a reason behing it! Thanks

Explanation / Answer

I think I can give a better counter example following the methodology given:

For example,

U = {1,2,3,4,5,6,7,8,9,10}

S1 = (2,5,8,9,10)

S2 = (1,2,3,5)

S3 = (1,2,3,9)

S4 = (4,5,6,7)

Now, first we select the largest set that is S1, after that largest set containing uncovered elements is S4 (algo has to go to last) ,then S2 & S3 provide same set of uncovered elements(1,3) in this step.

Hence algorithm fails to determine which to choose from S2 & S3.

Using Greedy Algorithm,

Greedy Method

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.