Solved

# Set Cover problem - algorithm

Posted on 2010-11-26

Hi,

Can someone please share a program in java which does the following.

if given the following sets as inputs,

a={1,2,3,8,9,10}

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

c={4,5,7}

d={5,6,7}

e={6,7,8,9,10}

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

the program will find all the combinations of the set and find out the minimum number of sets that together has all the elements of U.

In the above example, the minimum number is 2. set b and e together covers all of U.

So basically, it is a set covering problem. In the Set Covering problem, we are given a universe U, such that |U|=n, and sets S1,……,Sk are subsets of U. A set cover is a collection C of some of the sets from S1,……,Sk whose union is the entire universe U. Additionally, we must minimize the cost of the sets.

Thanks so much in advance.