%0 Conference Paper %1 mario2007approximating %A Boley, Mario %B Discovery Science %D 2007 %K approximation dataMining %P 68--77 %T On Approximating Minimum Infrequent and Maximum Frequent Sets %U http://dx.doi.org/10.1007/978-3-540-75488-6_8 %X 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 outto approximate a minimum infrequent set within a logarithmic factor one can show that there is no such algorithm for the maximizationproblem.

@inproceedings{mario2007approximating, 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 outto approximate a minimum infrequent set within a logarithmic factor one can show that there is no such algorithm for the maximizationproblem.}, added-at = {2009-08-12T15:54:02.000+0200}, author = {Boley, Mario}, biburl = {https://www.bibsonomy.org/bibtex/2b4086cabf5a1768cb517d3dae24ea287/mboley}, booktitle = {Discovery Science}, description = {SpringerLink - Buchkapitel}, interhash = {19cfadc9a0a9e371d07a97f0bd9bb96e}, intrahash = {b4086cabf5a1768cb517d3dae24ea287}, keywords = {approximation dataMining}, pages = {68--77}, timestamp = {2009-08-12T15:54:02.000+0200}, title = {On Approximating Minimum Infrequent and Maximum Frequent Sets}, url = {http://dx.doi.org/10.1007/978-3-540-75488-6_8}, year = 2007 }