2026-09-08T01:22:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26462 2026-09-05T19:44:19Z ddc:004 open_access

Online Correlation Clustering: Simultaneously Optimizing All 𝓁_p-Norms Davies, Sami Moseley, Benjamin Newman, Heather Online algorithms correlation clustering all-norms objective beyond-worst-case analysis The 𝓁_p-norm objectives for correlation clustering present a fundamental trade-off between minimizing total disagreements (the 𝓁₁-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(log⁴ 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 𝓁₁-norm in expectation. This work successfully translates the offline "all-norm" 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 𝓁₁-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 Ω(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 𝓁₁- and 𝓁_∞- norms are nearly tight in the AOS model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sami Davies and Benjamin Moseley and Heather Newman 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.73 urn:nbn:de:0030-drops-264620 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.73 eng https://creativecommons.org/licenses/by/4.0/legalcode