View Full Document

6 views

Unformatted text preview:

Correlation Clustering with a Fixed Number of Clusters Ioannis Giotis Venkatesan Guruswami Abstract We continue the investigation of problems concerning correlation clustering or clustering with qualitative information which is a clustering formulation that has been studied recently 5 7 8 3 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 from 13 In contrast when the number of clusters is not specified the problem of minimizing disagreements was shown to be APX hard 7 even though the maximization version admits a PTAS 1 Introduction In this work we investigate problems concerning an appealing formulation of clustering called correlation clustering or clustering using qualitative information that has been studied recently in several works including 6 17 5 7 8 3 2 4 The basic



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view corrclus-k and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view corrclus-k and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?