Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms

The ℓp-norm objectives for correlation clustering present a fundamental trade-off between minimizing total disagreements (the ℓ1-norm) and ensuring fairness to individual nodes (the ℓ_∞-norm). Surprisingly, in the offline setting it is possible to simultaneously approximate all ℓp-norms with a single clustering. Can this powerful guarantee be achieved in an online setting? This paper provides the first affirmative answer. We present a single algorithm for the online-with-a-sample (AOS) model that, given a small constant fraction of the input as a sample, produces one clustering that is simultaneously O(log4 n)-competitive for all ℓp-norms with high probability, O(log n)-competitive for the ℓ_∞-norm with high probability, and O(1)-competitive for the ℓ1-norm in expectation. This work successfully translates the offline "all-norms" guarantee to the online world. Our setting is motivated by a new hardness result that demonstrates a fundamental separation between these objectives in the standard random-order (RO) online model. Namely, while the ℓ1-norm is trivially O(1)-approximable in the RO model, we prove that any algorithm in the RO model for the fairness-promoting ℓ_∞-norm must have a competitive ratio of at least Omega(n1/3). This highlights the necessity of a different beyond-worst-case model. We complement our algorithm with lower bounds, showing our competitive ratios for the ℓ1- and ℓ_∞- norms are nearly tight in the AOS model.