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

### MINIMUM HITTING SET

- 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