Correlation Clustering with a Fixed Number of Clusters

Details Correlation Clustering with a Fixed Number of Clusters Correlation Clustering with a Fixed Number of Clusters

2005-04-06

arxiv.org/abs/cs/0504023v1

Computer Science

Data Structures and Algorithms

16 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Correlation Clustering with a Fixed Number of Clusters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Correlation Clustering with a Fixed Number of Clusters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Correlation Clustering with a Fixed Number of Clusters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-362311