Correlation Clustering: maximizing agreements via semidefinite programming Export

@inproceedings{citeulike:3477697, abstract = {We consider the Correlation Clustering problem introduced in [2]. Given a graph G = ( V,E ) where each edge is labeled either "+" (similar) or "-" (different), we want to cluster the nodes so that the + edges lie within the clusters and the -- edges lie between clusters. Specifically, we want to maximize agreements --- the number of + edges within clusters and -- edges between clusters. This problem is NP-Hard [2]. We give a 0.7666-approximation algorithm for maximizing agreements on any graph even when the edges have non-negative weights (along with labels) and we want to maximize the weight of agreements. These were posed as open problems in [2]. Previously the only results known were a trivial 0.5-approximation for arbitrary edge weighted graphs, and a PTAS with unit edge weights when | E | = Ω(| V | 2 ). Somewhat surprisingly, our algorithm always produces a clustering with at most 6 clusters . As a corollary we get a 0.7666-approximation algorithm for the k -clustering variant of the problem where we may create at most k clusters. A major component of this algorithm is a simple, easy-to-analyze algorithm that by itself achieves an approximation ratio of 0.75, opening at most 4 clusters.}, address = {Philadelphia, PA, USA}, author = {Swamy, Chaitanya}, booktitle = {SODA '04: Proceedings of the 15th annual ACM-SIAM Symposium On Discrete Algorithms}, citeulike-article-id = {3477697}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=982866}, isbn = {0-89871-558-X}, keywords = {clustering, graph, signed\_graph}, location = {New Orleans, Louisiana}, pages = {526--527}, posted-at = {2008-11-04 06:41:57}, priority = {0}, publisher = {Society for Industrial and Applied Mathematics}, title = {Correlation Clustering: maximizing agreements via semidefinite programming}, url = {http://portal.acm.org/citation.cfm?id=982866}, year = {2004} }

TY - CONF ID - citeulike:3477697 L3 - citeulike-article-id:3477697 N2 - We consider the Correlation Clustering problem introduced in [2]. Given a graph G = ( V,E ) where each edge is labeled either "+" (similar) or "-" (different), we want to cluster the nodes so that the + edges lie within the clusters and the -- edges lie between clusters. Specifically, we want to maximize agreements --- the number of + edges within clusters and -- edges between clusters. This problem is NP-Hard [2]. We give a 0.7666-approximation algorithm for maximizing agreements on any graph even when the edges have non-negative weights (along with labels) and we want to maximize the weight of agreements. These were posed as open problems in [2]. Previously the only results known were a trivial 0.5-approximation for arbitrary edge weighted graphs, and a PTAS with unit edge weights when | E | = Ω(| V | 2 ). Somewhat surprisingly, our algorithm always produces a clustering with at most 6 clusters . As a corollary we get a 0.7666-approximation algorithm for the k -clustering variant of the problem where we may create at most k clusters. A major component of this algorithm is a simple, easy-to-analyze algorithm that by itself achieves an approximation ratio of 0.75, opening at most 4 clusters. CY - New Orleans, Louisiana SN - 0-89871-558-X AD - Philadelphia, PA, USA EP - 527 TI - Correlation Clustering: maximizing agreements via semidefinite programming PB - Society for Industrial and Applied Mathematics T2 - SODA '04: Proceedings of the 15th annual ACM-SIAM Symposium On Discrete Algorithms SP - 526 KW - clustering KW - graph KW - signed_graph AU - Swamy, Chaitanya PY - 2004/// UR - http://portal.acm.org/citation.cfm?id=982866 ER -