SP7 M INIMUM H ITTING S ET

       
• I NSTANCE : Collection C of subsets of a finite set S .
• S OLUTION : A hitting set for C , i.e., a subset such that S' contains at least one element from each subset in C .
• M EASURE : Cardinality of the hitting set, i.e., |S'| .

• Good News: See M INIMUM S ET C OVER .
• Bad News: See M INIMUM S ET C OVER .
• Comment: Equivalent to M INIMUM S ET C OVER [ 27 ]. Therefore approximation algorithms and nonapproximability results for M INIMUM S ET C OVER will carry over to M INIMUM H ITTING S ET . 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 [ 352 ]. 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 [ 160 ].
• Garey and Johnson: SP8