Faster Deterministic Approximation Algorithms for Correlation Clustering
  and Cluster Deletion
  Correlation clustering is a framework for partitioning datasets based on
pairwise similarity and dissimilarity scores, and has been used for diverse
applications in bioinformatics, social network analysis, and computer vision.
Although many approximation algorithms have been designed for this problem, the
best theoretical results rely on obtaining lower bounds via expensive linear
programming relaxations. In this paper we prove new relationships between
correlation clustering problems and edge labeling problems related to the
principle of strong triadic closure. We use these connections to develop new
approximation algorithms for correlation clustering that have deterministic
constant factor approximation guarantees and avoid the canonical linear
programming relaxation. Our approach also extends to a variant of correlation
clustering called cluster deletion, that strictly prohibits placing negative
edges inside clusters. Our results include 4-approximation algorithms for
cluster deletion and correlation clustering, based on simplified linear
programs with far fewer constraints than the canonical relaxations. More
importantly, we develop faster techniques that are purely combinatorial, based
on computing maximal matchings in certain auxiliary graphs and hypergraphs.
This leads to a combinatorial 6-approximation for complete unweighted
correlation clustering, which is the best deterministic result for any method
that does not rely on linear programming. We also present the first
combinatorial constant factor approximation for cluster deletion.
