Next: MINIMUM GEOMETRIC DISK COVER
Up: Covering, Hitting, and Splitting
Previous: MINIMUM TEST COLLECTION
  Index
- INSTANCE:
Collection C of subsets of a finite set S.
- SOLUTION:
A hitting set for C, i.e., a subset
such that S'
contains at least one element from each subset in C.
- MEASURE:
Cardinality of the hitting set, i.e., |S'|.
- Good News:
See MINIMUM SET COVER.
- Bad News:
See MINIMUM SET COVER.
- Comment:
Equivalent to MINIMUM SET COVER [43].
Therefore approximation algorithms and nonapproximability results for
MINIMUM SET COVER will carry over to MINIMUM HITTING SET.
The constrained variation in which the input is extended with a subset
T of S, and the problem is to find the hitting set that contains the
largest number of elements from T,
is not approximable within
for some
[452].
Several special cases in which, given compact subsets of Rd, the goal is
to find a set of straight lines of minimum cardinality so that each of the
given subsets is hit by at least one line, are approximable [219].
- Garey and Johnson: SP8
Next: MINIMUM GEOMETRIC DISK COVER
Up: Covering, Hitting, and Splitting
Previous: MINIMUM TEST COLLECTION
  Index
Viggo Kann
1999-04-22