Metraipolis › archive › dc_0324cd131972
Online Correlation Clustering with Metric Weights — arXiv:2608.06566
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.06566
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-23T15:10:59.787Z
- SHA-256 of the archived text
d14bde395a98d8704fb5cdbca1b4e6fbd819930b0a12343d00166a1c71219972- Stable URL of this page
https://metraipolis.com/documento/dc_0324cd131972
How to cite
Online Correlation Clustering with Metric Weights — arXiv:2608.06566 — arXiv (en), https://arxiv.org/abs/2608.06566 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0324cd131972 (Metraipolis archive dc_0324cd131972, sha256 d14bde395a98d8704fb5cdbca1b4e6fbd819930b0a12343d00166a1c71219972)
BibTeX
@misc{dc0324cd131972,
title = {Online Correlation Clustering with Metric Weights — arXiv:2608.06566},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.06566},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0324cd131972; sha256 d14bde395a98d8704fb5cdbca1b4e6fbd819930b0a12343d00166a1c71219972},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.06566. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The standard online version of correlation clustering is prohibitively hard, as even randomized algorithms cannot achieve competitive ratio better than $\Omega(n)$. Prior works bypass this lower bound by relaxing the online model through recourse, random arrival order, or seeding the algorithm with an offline sample of the underlying input. We instead ask whether additional structure in the input itself can overcome this lower bound. We study weighted correlation clustering under probability constraints, where $w^+_{uv}+w^-_{uv}=1$ for every $uv$ edge, and triangle inequality constraints, where the negative weights $w^-$ satisfy triangle inequality. While this version of correlation clustering is well-studied in the offline setting, we initiate its online study and give a deterministic online algorithm that maintains a clustering whose total weighted disagreement cost is within an $O(1)$ factor of the offline optimum, against adversarial arrival order. This is the first constant-competitive online algorithm for a natural minimization variant of correlation clustering in the fully online model, and shows that metric consistency on the edge weights separates tractable from intractable online instances.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.06566 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-23T15:08:55.950Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).