On compressing frequent patterns

Dong Xin, Jiawei Han, Xifeng Yan and Hong Cheng
Data & Knowledge Engineering
Volume 60, Issue 1 , January 2007, Pages 5-29
http://dx.doi.org/10.1016/j.datak.2006.01.006

頻出パターンの数が膨大なので，それらを代表するようなパターンを求める問題を考えている．
この問題が集合被覆問題を特殊な場合として含んでいることを観察して，NP困難性や貪欲アルゴリズムの近似性などを導き，実際に実験もして効果を考察している．