Clustering and the Biclique Partition Problem
Document Type
Article
Publication Date
1-1-2008
Publication Title
Proceedings of the 41st Annual Hawaii International Conference on System Sciences
First page number:
475
Abstract
A technique for clustering data by common attribute values involves grouping rows and columns of a binary matrix to make the minimum number of submatrices all 1.s. As binary matrices can be viewed as adjacency matrices of bipartite graphs, the problem is equivalent to partitioning a bipartite graph into the smallest number of complete bipartite sub-graphs (commonly called .bicliques.). We show that the Biclique Partition Problem (BPP) does not have a polynomial time a-approximation algorithm, for any a = 1, unless P=NP. We also show that the Biclique Partition Problem, restricted to whether at most k bicliques are sufficient (i.e. BPP(k)) for each positive integer k, has a polynomial time 2-approximation algorithm. In addition, we give an O(VE) time algorithm and BPP(2), and an O(V) algorithm to find an optimum biclique partition of trees.
Language
eng
Repository Citation
Bein, D.,
Bein, W.,
Morales, L.,
Sudborough, H.
(2008).
Clustering and the Biclique Partition Problem.
Proceedings of the 41st Annual Hawaii International Conference on System Sciences
475.
http://dx.doi.org/10.1109/HICSS.2008.504