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 proceedingConference contributionpeer-review

2 Scopus citations

Abstract

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
Pages7-49
Number of pages43
Volume145
DOIs
StatePublished - 2008
Externally publishedYes

Publication series

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

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

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

Cite this