Paper by Erik D. Demaine

Reference:

Erik D. Demaine and Nicole Immorlica, “Correlation Clustering with Partial Information”, in Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM-APPROX 2003), Princeton, New Jersey, August 24–26, 2003, pages 1–13.

Abstract:

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.

Correlation clustering was introduced by Bansal, Blum, and Chawla [1], motivated by both document clustering and agnostic learning. They proved NP-hardness and gave constant-factor approximation algorithms for the special case in which the graph is complete (full information) and every edge has weight +1 or −1. We give an O(log n)-approximation algorithm for the general case based on a linear-programming rounding and the “region-growing” technique. We also prove that this linear program has a gap of Ω(log n), and therefore our approximation is tight under this approach. We also give an O(r³)-approximation algorithm for K_r, r-minor-free graphs. On the other hand, we show that the problem is APX-hard, and any o(log n)-approximation would require improving the best approximation algorithms known for minimum multicut.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (328k), gzipped PostScript (155k), and PDF (139k).

See information on file formats.

[Google Scholar search]

Related papers:

Clustering_TCS (Correlation Clustering in General Weighted Graphs)