Next:
SP7 MINIMUM HITTING
Up:
CoveringHitting, and Splitting
Previous:
SP5 MINIMUM EXACT
SP6 M
INIMUM
T
EST
C
OLLECTION
I
NSTANCE
: Collection
C
of subsets of a finite set
S
.
S
OLUTION
: A subcollection
such that for each pair of distinct elements
there is some set
that contains exactly one of
and
.
M
EASURE
: Cardinality of the subcollection, i.e.,
|C'|
.
Good News:
Approximable within
.
Comment:
Transformation to M
INIMUM
S
ET
C
OVER
[
200
]. Observe that every solution has cardinality at least
.
Garey and Johnson:
SP6
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
such that for each pair of distinct elements
there is some set
that contains exactly one of
and
.
.
.