- INSTANCE:
Collection
*C*of subsets of a finite set*S*. - SOLUTION:
A set cover for
*S*, i.e., a subset such that every element in*S*belongs to at least one member of*C'*. - MEASURE:
Sum of cardinalities of the subsets in the set cover, i.e.,
.

*Good News:*Approximable within [276].*Bad News:*As hard to approximate as MINIMUM SET COVER [365].*Comment:*Transformation from MINIMUM SET COVER. The only difference between MINIMUM SET COVER and MINIMUM EXACT COVER is the definition of the objective function.