2026-08-14T17:12:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2486 2024-03-06T10:33:26Z ddc:004 open_access

Online Correlation Clustering Mathieu, Claire Sankur, Ocan Schudy, Warren Correlation clustering online algorithms We study the online clustering problem where data items arrive in an online fashion. The algorithm maintains a clustering of data items into similarity classes. Upon arrival of v, the relation between v and previously arrived items is revealed, so that for each u we are told whether v is similar to u. The algorithm can create a new luster for v and merge existing clusters. When the objective is to minimize disagreements between the clustering and the input, we prove that a natural greedy algorithm is O(n)-competitive, and this is optimal. When the objective is to maximize agreements between the clustering and the input, we prove that the greedy algorithm is .5-competitive; that no online algorithm can be better than .834-competitive; we prove that it is possible to get better than 1/2, by exhibiting a randomized algorithm with competitive ratio .5+c for a small positive fixed constant c. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Claire Mathieu and Ocan Sankur and Warren Schudy 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2486 urn:nbn:de:0030-drops-24862 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2486 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode