Next:
SP6 MINIMUM TEST
Up:
CoveringHitting, and Splitting
Previous:
SP4 MINIMUM SET
-
I
NSTANCE
:
Collection
C
of subsets of a finite set
S
.
-
S
OLUTION
:
A set cover for
S
, i.e., a subset
such that every
element in
S
belongs to at least one member of
C'
.
-
M
EASURE
:
Sum of cardinalities of the subsets in the set cover, i.e.,
.
-
Good News:
Approximable within
[
194
].
-
Bad News:
As hard to approximate as M
INIMUM
S
ET
C
OVER
[
264
].
-
Comment:
Transformation from M
INIMUM
S
ET
C
OVER
.
The only difference between M
INIMUM
S
ET
C
OVER
and M
INIMUM
E
XACT
C
OVER
is the
definition of the objective function.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997