## 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,·,C_{min}+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 language | English (US) |
---|---|

Pages (from-to) | 174-185 |

Number of pages | 12 |

Journal | Electronic Notes in Theoretical Computer Science |

Volume | 82 |

Issue number | 4 |

DOIs | |

State | Published - Mar 2003 |

Externally published | Yes |

Event | International Workshop on Rough Sets in Knowledge Discovery and Soft Computing (Satellite Event for ETAPS 2003) - Warsaw, Poland Duration: Apr 12 2003 → Apr 13 2003 |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science