View article

In this work we study the problem of bipartite correlation clustering (BCC), a natural bipartite counterpart of the well-studied correlation clustering (CC) problem [N. Bansal, A. Blum, and S. Chawla, Machine Learning, 56 (2004), pp. 89--113], also referred to as graph editing [R. Shamir, R. Sharan, and D. Tsur, Discrete Appl. Math., 144 (2004), pp. 173--182]. Given a bipartite graph, the objective of BCC is to generate a set of vertex disjoint bicliques (clusters) that minimizes the symmetric difference to the original graph. The best-known approximation algorithm for BCC due to Amit [N. Amit, The Bicluster Graph Editing Problem, Master's Thesis, Tel Aviv University, Tel Aviv, Israel, 2004] guarantees an -approximation ratio. In this paper we present two algorithms. The first is a linear program based -approximation algorithm. Like the previous approximation algorithm, it requires solving a large convex problem, which becomes …