Approximate Dual Separation for the Cluster LP: a 1.387-approximation for Correlation Clustering

David García-Soriano, Antoine Schohn

We give a $(1.3865+\epsilon )$-approximation for correlation clustering on complete graphs, improving the previous best factor of $1.485+\epsilon$ of Cao et al. (STOC'24). Our first main contribu…