Computational Complexity Of Bi-clustering
Sharon Wulff · UWSpace (University of Waterloo) · 2008
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii 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 ma-trices. Such problems have arisen recently in systems biology where researchers have inferred functional classifications of biological agents based on their pair-wise 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