MINIMUM EXACT COVER

• INSTANCE: Collection C of subsets of a finite set S.
• SOLUTION: A set cover for S, i.e., a subset $C'\subseteq C$ 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., $$\sum\limits_{c\in C'} \vert c\vert$$.

  
  

• Good News: Approximable within $1+\ln\vert S\vert$ [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.