Abstract
The maximum cardinality of a frequent set as well as the minimum cardinality of an infrequent set are important characteristic numbers in frequent (item) set mining. Gunopulos et al. [10] have shown that finding a maximum frequent set is NP-hard. In this paper I show that the minimization problem is also NP-hard. As a next step I investigate whether these problems can be approximated. While a simple greedy algorithm turns out to approximate a minimum infrequent set within a logarithmic factor one can show that there is no such algorithm for the maximization problem.
| Original language | English |
|---|---|
| Title of host publication | Discovery Science - 10th International Conference, DS 2007, Proceedings |
| Publisher | Springer |
| Pages | 68-77 |
| Number of pages | 10 |
| ISBN (Print) | 9783540754879 |
| Publication status | Published - 2007 |
| Externally published | Yes |
| Event | 10th International Conference on Discovery Science, DS 2007 - Sendai, Japan Duration: 1 Oct 2007 → 4 Oct 2007 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 4755 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 10th International Conference on Discovery Science, DS 2007 |
|---|---|
| Country/Territory | Japan |
| City | Sendai |
| Period | 1/10/07 → 4/10/07 |