Partial covers, reducts and decision rules

Mikhail Ju Moshkov*, Marcin Piliszczuk, Beata Zielosko

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

5 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationPartial Covers, Reducts and Decision Rules in Rough Sets
Subtitle of host publicationTheory and Applications
EditorsMikhail Moshkov, Beata Zielosko, Marcin Piliszczuk
Number of pages43
StatePublished - 2008

Publication series

NameStudies in Computational Intelligence
ISSN (Print)1860-949X

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Partial covers, reducts and decision rules'. Together they form a unique fingerprint.

Cite this