On approximating minimum infrequent and maximum frequent sets

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

4 Citations (Scopus)

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 languageEnglish
Title of host publicationDiscovery Science - 10th International Conference, DS 2007, Proceedings
PublisherSpringer
Pages68-77
Number of pages10
ISBN (Print)9783540754879
Publication statusPublished - 2007
Externally publishedYes
Event10th International Conference on Discovery Science, DS 2007 - Sendai, Japan
Duration: 1 Oct 20074 Oct 2007

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume4755
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Discovery Science, DS 2007
Country/TerritoryJapan
CitySendai
Period1/10/074/10/07

Cite this