@inproceedings{97006736db8b411d98f56492c2f2f070,

title = "On the complexity of generating maximal frequent and minimal infrequent sets",

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.",

keywords = "Data mining, Dualization, Frequent sets, Hitting sets, Independent sets, Infrequent sets, Transversals",

author = "E. Boros and V. Gurvich and L. Khachiyan and K. Makino",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002 ; Conference date: 14-03-2002 Through 16-03-2002",

year = "2002",

doi = "https://doi.org/10.1007/3-540-45841-7_10",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "133--141",

editor = "Helmut Alt and Afonso Ferreira",

booktitle = "STACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",

address = "Germany",

}