Greedy algorithm for set cover in context of knowledge discovery problems

Mikhail Moshkov*

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

10 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)174-185
Number of pages12
JournalElectronic Notes in Theoretical Computer Science
Volume82
Issue number4
DOIs
StatePublished - Jan 1 2003
EventInternational Workshop on Rough Sets in Knowledge Discovery and Soft Computing (Satellite Event for ETAPS 2003) - Warsaw, Poland
Duration: Apr 12 2003Apr 13 2003

Keywords

  • Data table
  • Greedy algorithm
  • Knowledge discovery
  • Partial cover

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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