Online Correlation Clustering with Metric Weights
TL;DR
This work gives a deterministic online algorithm that maintains a clustering whose total weighted disagreement cost is within an $O(1)$ factor of the offline optimum, against adversarial arrival order, and shows that metric consistency on the edge weights separates tractable from intractable online instances.
Abstract
The standard online version of correlation clustering is prohibitively hard, as even randomized algorithms cannot achieve competitive ratio better than $\Omega(n)$. Prior works bypass this lower bound by relaxing the online model through recourse, random arrival order, or seeding the algorithm with an offline sample of the underlying input. We instead ask whether additional structure in the input itself can overcome this lower bound. We study weighted correlation clustering under probability constraints, where $w^+_{uv}+w^-_{uv}=1$ for every $uv$ edge, and triangle inequality constraints, where the negative weights $w^-$ satisfy triangle inequality. While this version of correlation clustering is well-studied in the offline setting, we initiate its online study and give a deterministic online algorithm that maintains a clustering whose total weighted disagreement cost is within an $O(1)$ factor of the offline optimum, against adversarial arrival order. This is the first constant-competitive online algorithm for a natural minimization variant of correlation clustering in the fully online model, and shows that metric consistency on the edge weights separates tractable from intractable online instances.