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 V
1∪V
3∪V
4={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).