Online Correlation Clustering with Metric Weights
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...