Partial covers, reducts and decision rules

In this chapter, we consider theoretical and experimental results on partial decision reducts and partial decision rules. These investigations are based on the study of partial covers. Based on the technique created by Ślȩzak in [50, 52], we generalize well known results of Feige [7], and Raz and Safra [43] on the precision of approximate polynomial algorithms for exact cover minimization (construction of an exact cover with minimal cardinality) to the case of partial covers. From obtained results and results of Slavík [47, 48] on the precision of greedy algorithm for partial cover construction it follows that, under some natural assumptions on the class NP, the greedy algorithm for partial cover construction is close (from the point of view of precision) to the best polynomial approximate algorithms for partial cover minimization. © 2008 Springer-Verlag Berlin Heidelberg.