A set S that has a non-empty intersection with every set in a collection of sets C is called a hitting set of C. If no elements can be removed from S without violating the hitting set property, then we say that S is minimal. Several interesting problems can in part be formulated as that of having to ®nd one or more minimal hitting sets. Many of these problems require proper solutions, but sometimes approximate solutions suce. We de®ne an r-approximate hitting set as a set that intersects at least a fraction r of the sets in C. This notion is extended to the case, where C is a weighted multiset, and properties of r are explored with respect to simpli®cation of C by absorption of supersets. Also, approximations of reducts from rough set theory are de®ned by means of minimal r-approximate hitting sets, and some links to the notion of dynamic reducts are established.
The most common use of reducts are as templates for the generation of minimal classi®cation rules from empirical data. A genetic algorithm is devised to compute r-approximate hitting sets, and applied to induce classi®ers from selected real-world databases. These classi®ers are then compared to those generated from proper reducts and dynamic reducts, respectively. The improvement in discriminatory ability yielded by the r-approximate reduct based classi®ers was statistically signi®cant (p `0X05). Furthermore, they were smaller, i.e., had fewer rules.