MINIMUM EXACT COVER

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 $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., $\displaystyle\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.

Viggo Kann
2000-03-20