The smallest number of containers that contain all given elements

Question

Suppose C refers to a set of containers {c1,c2,c3....cn}, where each of these containers contains a finite set of integers {i1,i2,i3...im}. Further, suppose that it is possible for an integer to exist in more than one container. Given a finite set of integers S {s1,s2,s3...sz}, find the size of the smallest subset of C that contains all integers in S.

Note that there could be thousands of containers each with hundreds of integers. Therefore, brute force is slow for solving this problem.

I tried to solve the problem using Greedy algorithm. That is, each time I select the container with the largest number of integers in the set S, but I failed!

Can anyone suggest a fast algorithm for this problem?

Answer 1

This is the well known set cover problem. It is NP-hard — in fact, its decision version was one of the canonical NP-complete problems and was among the 21 problems included in Karp's 1972 paper — and so no efficient algorithm is known. Unless you can identify some special extra structure to the problem, you will have to be satisfied with an approximate result: that is, a subset of C whose union contains S, which but which is not necessarily the smallest such subset of C.

The greedy algorithm is probably your best bet: it finds a collection of sets that is no more than O(log |C|) times the size of the smallest such collection.

You say that you were unable to get the greedy algorithm to work. I think this is probably because you failed to implement it correctly. You describe your algorithm like this:

each time I select the container with the largest number of integers in the set S

but the rule in the usual greedy algorithm is to select at each stage the container with the largest number of integers in the set S that are not in any container selected so far.