arXiv:2607.27829 · v3

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

首次提交 2026-07-30 16:07

版本更新 2026-11-03 21:18

雷达观测 2026-11-04 23:39

摘要

We give a $(1.3865+ε)$-approximation for correlation clustering on complete graphs, improving the previous best factor of $1.485+ε$ of Cao et al. (STOC'24). Our first main contribution is an efficient weak separation oracle for the cluster-LP dual. Given signed vertex weights $q$, it either finds a set $S$ with $q(S)>cost(S)$ or certifies that $q/(1+ε)$ is dual feasible, where $cost(S)$ measures the correlation clustering disagreements attributed to $S$ in any clustering in which $S$ is a cluster. Via the ellipsoid method, this yields $(1+ε)$-approximate primal and dual solutions for the fractional cluster LP in deterministic time $2^{poly(1/ε)}n^{O(1)}$ . The separator works directly on the original instance, without global preclustering: a novel localization argument restricts the search to a small universe, where weak regularity handles the resulting dense quadratic minimization. Complementing this result, we prove that exact dual separation and cluster-LP optimization are NP-hard, even for complete unweighted instances. Our second main contribution is a new rounding of the cluster LP. It combines cluster-based rounding with a continuous conditional pivot rule, and its analysis relies on single variance inequality with explicit weights. This bounds the cluster-LP integrality gap by $1.3865$, near its known lower bound of $4/3$, and gives a per-instance primal--dual certificate of approximation. Finally, we extend our separator to obtain a $(1.92+ε)$-approximation for seeded correlation clustering (where each cluster may contain at most one seed from a prescribed seed set), and to bounded-weight instances, yielding a deterministic polynomial-time approximate implementation of the cluster-insertion primitive used in combinatorial correlation clustering.

作者备注：revised organization to match conference submission