Next: MINIMUM TEST COLLECTION Up: Covering, Hitting, and Splitting Previous: MINIMUM SET COVER Index

### MINIMUM EXACT COVER

- 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 [261].

- Bad News: As hard to approximate as MINIMUM SET COVER [346].

- Comment: Transformation from MINIMUM SET COVER. The only difference between MINIMUM SET COVER and MINIMUM EXACT COVER is the definition of the objective function.