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 α-approximation algorithm, for any α ≥ 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.
['Doina Bein', 'Linda Morales', 'Wolfgang W. Bein', 'Charles Shields', 'Z. Meng', 'Ivan Hal Sudborough']
Clustering and the Biclique Partition Problem