# Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms

arXiv: https://arxiv.org/abs/2510.15076 · HTML: https://mlsanity.com/paper/2510.15076/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 41 references that are in the map.
- First posted on arXiv 16 Oct 2025.

## Builds on (most cited first, 24 of 24)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Semi-Online Bipartite Matching](https://mlsanity.com/paper/1812.00134/) (2018)
- [Approximation Algorithms for Minimum Norm and Ordered Optimization Problems](https://mlsanity.com/paper/1811.05022/) (2018)
- [Correlation Clustering and Biclustering with Locally Bounded Errors](https://mlsanity.com/paper/1506.08189/) (2015)
- [Competitive Analysis with a Sample and the Secretary Problem](https://mlsanity.com/paper/1907.05350/) (2019)
- [Which Lp norm is the fairest? Approximations for fair facility location across all "p"](https://mlsanity.com/paper/2211.14873/) (2022)
- [Local Guarantees in Graph Cuts and Clustering](https://mlsanity.com/paper/1704.00355/) (2017)
- [Consistent k-Median: Simpler, Better and Robust](https://mlsanity.com/paper/2008.06101/) (2020)
- [Consistent k-Clustering for General Metrics](https://mlsanity.com/paper/2011.06888/) (2020)
- [Fast Combinatorial Algorithms for Min Max Correlation Clustering](https://mlsanity.com/paper/2301.13079/) (2023)
- [Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds](https://mlsanity.com/paper/1411.0547/) (2014)
- [Online Weighted Matching with a Sample](https://mlsanity.com/paper/2104.05771/) (2021)
- [Understanding the Cluster LP for Correlation Clustering](https://mlsanity.com/paper/2404.17509/) (2024)
- [A 4-approximation algorithm for min max correlation clustering](https://mlsanity.com/paper/2310.09196/) (2023)
- [Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees](https://mlsanity.com/paper/2311.03230/) (2023)
- [Set Covering with Our Eyes Wide Shut](https://mlsanity.com/paper/2304.02063/) (2023)
- [Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering](https://mlsanity.com/paper/2410.09321/) (2024)
- [Min-Max Correlation Clustering via Neighborhood Similarity](https://mlsanity.com/paper/2502.12519/) (2025)
- [Improved Bounds for Distributed Load Balancing](https://mlsanity.com/paper/2008.04148/) (2020)

## Abstract (arXiv)

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.