Set Cover Problem

Set Cover Problem

Given a universe U of n elements, a collection of subsets of U say S = {S₁, S₂…,S_m} where every subset S_i has an associated cost. Find a minimum cost subcollection of S that covers all elements of U.

There is no polynomial time solution available for this problem as the problem is a known NP-Hard problem. There is a polynomial time Greedy approximate algorithm, the greedy algorithm provides a Log n approximate algorithm.

2-Approximate Greedy Algorithm:

Let U be the universe of elements, {S₁, S₂, … S_m} be collection of subsets of U and Cost(S₁), C(S₂), … Cost(S_m) be costs of subsets.

1) Let I represents set of elements included so far.  Initialize I = {}

2) Do following while I is not same as U.

    a) Find the set S_i in {S₁, S₂, ... S_m} whose cost effectiveness is

       smallest, i.e., the ratio of cost C(S_i) and number of newly added

       elements is minimum.

       Basically we pick the set for which following value is minimum.

           Cost(S_i) / |S_i - I|

    b) Add elements of above picked S_i to I, i.e.,  I = I U S_i

Example:

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

   S = {S₁,S₂,S₃}

    S₁ = {4,1,3},    Cost(S₁) = 5

   S₂ = {2,5},      Cost(S₂) = 10

   S₃ = {1,4,3,2},  Cost(S₃) = 3

Output: Minimum cost of set cover is 13 and set cover is {S2, S3}