Conference Proceedings

Correlation clustering generalized

DF Gleich, N Veldt, A Wirth

Proceedings of the 29th International Symposium on Algorithms and Computation | Schloss Dagstuhl | Published : 2018


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 Θ(log n) integrality gap for a certain choice of the parameter λ. 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 λ. MotifCC generalizes co..

View full abstract