Greedy Algorithm for Set Cover in Context of Knowledge Discovery Problems

✍ Scribed by Mikhail Ju. Moshkov

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 750 KB
• Volume: 82
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(04)80716-3

✦ Synopsis

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_{\text {min }}). In the case of (90 %)-cover, for example, in the capacity of such function we can take the function (2.31 \cdot 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.