Computational Complexity Of Bi-clustering
Abstract
In this work we formalize a new natural objective (or cost) function
for bi-clustering - Monochromatic bi-clustering. Our objective function is
suitable for detecting meaningful homogenous clusters based on
categorical valued input matrices. Such problems have arisen recently in
systems biology where researchers have inferred functional classifications
of biological agents based on their pairwise interactions. We
analyze the computational complexity of the resulting optimization
problems. We show that finding optimal solutions is NP-hard and
complement this result by introducing a polynomial time
approximation algorithm for this bi-clustering task. This is the first positive
approximation guarantee for bi-clustering algorithms. We also show
that bi-clustering with our objective function can be viewed as a
generalization of correlation clustering.
Collections
Cite this version of the work
Sharon Jay Wulff
(2008).
Computational Complexity Of Bi-clustering. UWSpace.
http://hdl.handle.net/10012/3900
Other formats