Next: MINIMUM TEST COLLECTION
Up: Covering, Hitting, and Splitting
Previous: MINIMUM SET COVER
  Index
- 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.
Viggo Kann
1999-04-22