Heather Newman

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms

2025 · arXiv (Cornell University)

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 …