Partial covers, reducts and decision rules

Mikhail Ju Moshkov, Marcin Piliszczuk, Beata Zielosko

Research output: Contribution to journalArticlepeer-review

3 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. © 2008 Springer-Verlag Berlin Heidelberg.
Original languageEnglish (US)
Pages (from-to)7-49
Number of pages43
JournalStudies in Computational Intelligence
StatePublished - Sep 18 2008
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2023-09-21

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