Andreas Kalavas

Towards Better-than-2 Approximation for Constrained Correlation Clustering

In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the sum of the number of edges across different clusters and the number of non-edges within clusters. In the constrained version of this problem,…