On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling
arXiv:2602.13684v1 Announce Type: new Abstract: Correlation Clustering (CC) is a fundamental unsupervised learning primitive whose strongest LP-based approximation guarantees require $\Theta(n^3)$ triangle inequality constraints and …