Computational Complexity Of Bi-clustering

Bi-Clustering;NP-hardness;Polynomial time approximation scheme (PTAS);correlation clustering;Computer Science

Wulff, Sharon Jay

University of Waterloo

关键词: Bi-Clustering;    NP-hardness;    Polynomial time approximation scheme (PTAS);    correlation clustering;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/3900/1/thesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In this work we formalize a new natural objective (or cost) functionfor bi-clustering - Monochromatic bi-clustering. Our objective function issuitable for detecting meaningful homogenous clusters based oncategorical valued input matrices. Such problems have arisen recently insystems biology where researchers have inferred functional classificationsof biological agents based on their pairwise interactions. Weanalyze the computational complexity of the resulting optimizationproblems. We show that finding optimal solutions is NP-hard andcomplement this result by introducing a polynomial timeapproximation algorithm for this bi-clustering task. This is the first positiveapproximation guarantee for bi-clustering algorithms. We also showthat bi-clustering with our objective function can be viewed as ageneralization of correlation clustering.