2026-08-15T19:04:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9992 2024-03-06T10:45:17Z ddc:004 open_access

Correlation Clustering Generalized Gleich, David F. Veldt, Nate Wirth, Anthony Correlation Clustering Approximation Algorithms We present new results for LambdaCC and MotifCC, two recently introduced variants of the well-studied correlation clustering problem. Both variants are motivated by applications to network analysis and community detection, and have non-trivial approximation algorithms. We first show that the standard linear programming relaxation of LambdaCC has a Theta(log n) integrality gap for a certain choice of the parameter lambda. This sheds light on previous challenges encountered in obtaining parameter-independent approximation results for LambdaCC. We generalize a previous constant-factor algorithm to provide the best results, from the LP-rounding approach, for an extended range of lambda. MotifCC generalizes correlation clustering to the hypergraph setting. In the case of hyperedges of degree 3 with weights satisfying probability constraints, we improve the best approximation factor from 9 to 8. We show that in general our algorithm gives a 4(k-1) approximation when hyperedges have maximum degree k and probability weights. We additionally present approximation results for LambdaCC and MotifCC where we restrict to forming only two clusters. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David F. Gleich and Nate Veldt and Anthony Wirth 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.44 urn:nbn:de:0030-drops-99925 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.44 eng https://creativecommons.org/licenses/by/3.0/legalcode