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_14: We introduce a new graph parameter, called the Grothendieck constant of a graph G=(V,E), which is defined as the least constant K such that for every A:E→ℝ, @math The classical Grothendieck inequality corresponds to the case of bipartite graphs, but the case of general graphs is shown to have various algorithmic applications. Indeed, our work is motivated by the algorithmic problem of maximizing the quadratic form ∑ u,v ∈E A(u,v)ϕ(u)ϕ(v) over all ϕ:V→ -1,1 , which arises in the study of correlation clustering and in the investigation of the spin glass model. We give upper and lower estimates for the integrality gap of this program. We show that the integrality gap is (O( ( G )) ), where ( ( G ) ) is the Lovasz Theta Function of the complement of G, which is always smaller than the chromatic number of G. This yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs G. We also show that the maximum possible integrality gap is always at least Ω(log ω(G)), where ω(G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n vertices with no loops is Θ(logn). More generally, the maximum possible integrality gap for any perfect graph with chromatic number n is Θ(logn). The lower bound for the complete graph improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settles a problem of Megretski and of Charikar and Wirth.
@cite_16: This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x spl isin -1, 1 sup n such that x sup T Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in spl Omega (1 logn). This quadratic programming problem can be seen as an extension to that of maximizing x sup T Ay (where y's components are also spl plusmn 1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an spl Omega (1 logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.
Another problem that has been considered, let us call it , is that of maximizing correlation, defined to be the difference between the number of agreements and disagreements. A factor @math approximation for on complete graphs is presented in @cite_16 . Recently @cite_14 showed an integrality gap of @math for the underlying semidefinite program used in @cite_16 . They also prove that an approximation of @math can be achieved on general graphs @math , where @math is the Lov ' a sz Theta Function.