MINIMUM HITTING SET

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 $S'\subseteq S$ such that S' contains at least one element from each subset in C.
MEASURE: Cardinality of the hitting set, i.e., $\vert S'\vert$ .
Good News: See MINIMUM SET COVER.
Bad News: See MINIMUM SET COVER.
Comment: Equivalent to MINIMUM SET COVER [46]. 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 $\vert S\vert^{\varepsilon }$ for some $\varepsilon >0$ [476]. Several special cases in which, given compact subsets of , 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 [236].
Garey and Johnson: SP8

Next: MINIMUM GEOMETRIC DISK COVER Up: Covering, Hitting, and Splitting Previous: MINIMUM TEST COLLECTION Index

Viggo Kann
2000-03-20