We continue the investigation of problems concerning correlation clustering or clustering with qualitative information, which is a clustering formulation that has been studied recently. The basic setup here is that we are given as input a complete graph on n nodes (which correspond to nodes to be clustered) whose edges are labeled + (for similar pairs of items) and - (for dissimilar pairs of items). Thus we have only as input qualitative information on similarity and no quantitative distance measure between items. The quality of a clustering is measured in terms of its number of agreements, which is simply the number of edges it correctly classifies, that is the sum of number of - edges whose endpoints it places in different clusters plus the number of + edges both of whose endpoints it places within the same cluster. In this paper, we study the problem of finding clusterings that maximize the number of agreements, and the complementary minimization version where we seek clusterings that minimize the number of disagreements. We focus on the situation when the number of clusters is stipulated to be a small constant k. Our main result is that for every k, there is a polynomial time approximation scheme for both maximizing agreements and minimizing disagreements. (The problems are NP-hard for every k >= 2.) The main technical work is for the minimization version, as the PTAS for maximizing agreements follows along the lines of the property tester for Max k-CUT. In contrast, when the number of clusters is not specified, the problem of minimizing disagreements was shown to be APX-hard, even though the maximization version admits a PTAS.
@cite_7: 
@cite_3: We consider the Correlation Clustering problem introduced in [2]. Given a graph G = (V,E) where each edge is labeled either "+" (similar) or "-" (different), we want to cluster the nodes so that the + edges lie within the clusters and the -- edges lie between clusters. Specifically, we want to maximize agreements --- the number of + edges within clusters and -- edges between clusters. This problem is NP-Hard [2]. We give a 0.7666-approximation algorithm for maximizing agreements on any graph even when the edges have non-negative weights (along with labels) and we want to maximize the weight of agreements. These were posed as open problems in [2]. Previously the only results known were a trivial 0.5-approximation for arbitrary edge weighted graphs, and a PTAS with unit edge weights when |E| = Ω(|V|2). Somewhat surprisingly, our algorithm always produces a clustering with at most 6 clusters. As a corollary we get a 0.7666-approximation algorithm for the k-clustering variant of the problem where we may create at most k clusters. A major component of this algorithm is a simple, easy-to-analyze algorithm that by itself achieves an approximation ratio of 0.75, opening at most 4 clusters.
@cite_19: We consider the following general correlation-clustering problem [1]: given a graph with real edge weights (both positive and negative), partition the vertices into clusters to minimize the total absolute weight of cut positive edges and uncut negative edges. Thus, large positive weights (representing strong correlations between endpoints) encourage those endpoints to belong to a common cluster; large negative weights encourage the endpoints to belong to different clusters; and weights with small absolute value represent little information. In contrast to most clustering problems, correlation clustering specifies neither the desired number of clusters nor a distance threshold for clustering; both of these parameters are effectively chosen to be the best possible by the problem definition.
@cite_15: We solve several open problems concerning the correlation clustering problem introduced by Bansal, Blum and Chawla [1]. We give an equivalence argument between these problems and the multicut problem. This implies an O(log n) approximation algorithm for minimizing disagreements on weighted and unweighted graphs. The equivalence also implies that these problems are APX-hard and suggests that improving the upper bound to obtain a constant factor approximation is non trivial. We also briefly discuss some seemingly interesting applications of correlation clustering.
@cite_11: We consider the problem of clustering a collection of elements based on pairwise judgments of similarity and dissimilarity. N. (2002) cast the problem thus: given a graph G whose edges are labeled "+" (similar) or "-" (dissimilar), partition the vertices into clusters so that the number of pairs correctly (resp. incorrectly) classified with respect to the input labeling is maximized (resp. minimized). Complete graphs, where the classifier labels every edge, and general graphs, where some edges are not labeled, are both worth studying. We answer several questions left open by N. (2002) and provide a sound overview of clustering with qualitative information. We give a factor 4 approximation for minimization on complete graphs, and a factor O(log n) approximation for general graphs. For the maximization version, a PTAS for complete graphs is shown by N. (2002); we give a factor 0.7664 approximation for general graphs, noting that a PTAS is unlikely by proving APX-hardness. We also prove the APX-hardness of minimization on complete graphs.
The problems on general graphs have also received attention. It is known that both and are APX-hard @cite_7 @cite_11 . Using a connection to minimum multicut, several groups @cite_11 @cite_19 @cite_15 presented an @math approximation algorithm for . In fact, it was noted in @cite_15 that the problem is as hard to approximate as minimum multicut (and so this @math factor seems very hard to improve). For the maximization version, algorithms with performance ratio better than @math are known for @cite_11 @cite_3 . The latter work by Swamy @cite_3 shows that a factor @math approximation can also be achieved when the number of clusters is specified (i.e., for k for @math ).