  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.
