arXiv:2510.15076v1 Announce Type: new
Abstract: The $ell_p$-norm objectives for correlation clustering present a fundamental trade-off between minimizing total disagreements (the $ell_1$-norm) and ensuring fairness to individual nodes (the $ell_infty$-norm). Surprisingly, in the offline setting it is possible to simultaneously approximate all $ell_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(log^4 n)$-competitive for all $ell_p$-norms with high probability, $O(log n)$-competitive for the $ell_infty$-norm with high probability, and $O(1)$-competitive for the $ell_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 $ell_1$-norm is trivially $O(1)$-approximable in the RO model, we prove that any algorithm in the RO model for the fairness-promoting $ell_infty$-norm must have a competitive ratio of at least $Omega(n^{1/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 $ell_1$- and $ell_infty$- norms are nearly tight in the AOS model.