Constrained Correlation Clustering: Towards Optimality
This work identifies Constrained Correlation Clustering as a variant of Correlation Clustering for which optimal approximations might be within reach, and significantly tighten the gap, by showing that the optimal approximation factor lies in $[2,\frac{16}{7}-\gamma)$ for a small constant $0$.