The (minimal) SET COVER problem is the following:

Given N and a collection of sets {V1,...,Vn} for which ∪i=1n Vi = {1,...,N} and a number k, determine whether there exist indices n1,...,nk for which ∪i=1k Vni = {1,...,N}.

For example, if N=5 and

V1 = {1,2,3}
V2 = {1,5}
V3 = {2,4}
V4 = {4,5}
then we may solve SET COVER for any k≥3, since V1∪V3∪V4={1,2,3,4,5}, but not for any k<3.

SET COVER is known to be NP-complete (for instance, by easy reduction to vertex cover, but also more directly). However, it is known that the greedy algorithm can achieve a value of k within approximately ln(n) times the minimal value of k (the precise value is the n'th harmonic number Hn=1+1/2+...+1/n).

Log in or register to write something here or to contact authors.