The (minimal) SET COVER problem is the following:

Given N and a collection of sets {V_{1},...,V_{n}} for which ∪_{i=1}^{n} V_{i} = {1,...,N} and a number k, determine whether there exist indices n_{1},...,n_{k} for which ∪_{i=1}^{k} V_{ni} = {1,...,N}.

For example, if N=5 and

V_{1} = {1,2,3}

V_{2} = {1,5}

V_{3} = {2,4}

V_{4} = {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 H_{n}=1+1/2+...+1/n).