%0 Journal Article %1 keyhere %A Boros, E. %A Gurvich, V. %A Khachiyan, L. %A Makino, K. %D 2002 %J STACS 2002 %K complexity frequentSetMining listing seminar %P 733--733 %T On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets %U http://dx.doi.org/10.1007/3-540-45841-7_10 %X Let A be an m × n binary matrix, t ∈,1,… ,m be a threshold, and ε > 0 be a positive parameter. We show that given a family of O(nε) maximal t-frequent column sets for A, it is NP-complete to decide whether A has any further maximal t-frequent sets, or not, even when the number of such additional maximal t-frequent column sets may be exponentially large. In contrast, all minimal t-infrequent sets of columns of A can be enumerated in incremental quasi-polynomial time. The proof of the latter result follows from the inequality α ≤ (m-t+1)β, where α and β are respectively the numbers of all maximal t-frequent and all minimal t-infrequent sets of columns of the matrix A. We also discuss the complexity of generating all closed t-frequent column sets for a given binary matrix.

@article{keyhere, abstract = {Let A be an m × n binary matrix, t ∈,{1,… ,m} be a threshold, and ε > 0 be a positive parameter. We show that given a family of O(nε) maximal t-frequent column sets for A, it is NP-complete to decide whether A has any further maximal t-frequent sets, or not, even when the number of such additional maximal t-frequent column sets may be exponentially large. In contrast, all minimal t-infrequent sets of columns of A can be enumerated in incremental quasi-polynomial time. The proof of the latter result follows from the inequality α ≤ (m-t+1)β, where α and β are respectively the numbers of all maximal t-frequent and all minimal t-infrequent sets of columns of the matrix A. We also discuss the complexity of generating all closed t-frequent column sets for a given binary matrix.}, added-at = {2008-06-03T12:22:01.000+0200}, author = {Boros, E. and Gurvich, V. and Khachiyan, L. and Makino, K.}, biburl = {https://www.bibsonomy.org/bibtex/207b7d4c5e266a206b3e95a0862f7cc6b/mboley}, description = {SpringerLink - Book Chapter}, interhash = {860b1521d6766d7a67f509a75a83b007}, intrahash = {07b7d4c5e266a206b3e95a0862f7cc6b}, journal = {STACS 2002}, keywords = {complexity frequentSetMining listing seminar}, pages = {733--733}, timestamp = {2009-03-25T18:00:33.000+0100}, title = {On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets}, url = {http://dx.doi.org/10.1007/3-540-45841-7_10}, year = 2002 }