The Set Cover problem is defined thus: Given a universal set U and a set of subs

Question

The Set Cover problem is defined thus: Given a universal set U and a set of subsets s-: {si, S2, . . . , Sm} of? find the smallest number of subsets such that their union equals U. For example U= {1.2, 3, 4, 5), Si-(1,3, 5),S= {2.4),S3_ {1.2.3}, S4=(2, 3, 4} we can choose S?, S2 and this is clearly optimal since we cannot cover U with only one set. Here is an algorithm claiming to solve the Set Cover problem: Pick the largest subset (in case of ties, choose at random) call it T1. Delete the elements of Ti from all remaining subsets Repeat the procedure with the, now smaller, sets to get T2. Stop when you have covered the universal set. Either provide an argument that this greedy algorithm is correct (argue that it produces a cover and argue that the cover is minimal) or provide a counterexample.

Explanation / Answer

Algorithm is correct:

we can prove it by contradiction:

Lets say that this alogorithm gave a number n and assume it is incorrect and there
is correct value less than n

This means that at any one step or some steps we chose a subset whose cardinality is
less than some other subset. But this is against the step in the algorithm which
selects the subset of maximum cardinality. hence n has to be the correct answer

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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