Greedy algorithm for set cover in context of knowledge discovery problems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations


In the paper some problems connected with a process of knowledge discovery are considered. These problems are reduced to the set cover problem. It is known that under a plausible assumption on the class N P the greedy algorithm is close to best approximate polynomial algorithms for the set cover problem solving. Unfortunately, the performance ratio of this algorithm grows almost as natural logarithm on the cardinality of covered set. Instead of usual greedy algorithm we consider greedy algorithm with threshold. This algorithm constructs a partial cover, which covers at least a fixed part (for example, 90%) of the set. We prove that the cardinality of constructed partial cover is bounded from above by a linear function on the minimal cardinality of exact cover C min. In the case of 90% -cover, for example, in the capacity of such function we can take the function 2.31,·,Cmin+1. This bound is independent of the cardinality of covered set. Notice that the concept of partial cover in context of knowledge discovery problems is very close to the concept of approximate reduct. © 2003 Published by Elsevier Science B.V.
Original languageEnglish (US)
Title of host publicationElectronic Notes in Theoretical Computer Science
Number of pages12
StatePublished - Jan 1 2003
Externally publishedYes

Bibliographical note

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Greedy algorithm for set cover in context of knowledge discovery problems'. Together they form a unique fingerprint.

Cite this