Paper Info
Title
Online Correlation Clustering
Abstract
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 cluster 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.
Year
DOI
Venue
2010
10.4230/LIPIcs.STACS.2010.2486
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
correlation clustering,online algorithms
Journal
5
ISSN
Citations 
PageRank 
1868-8969
3
0.41
References 
Authors
8
3
Name
Order
Citations
PageRank
Claire Mathieu145225.78
Ocan Sankur210514.76
Warren Schudy322112.08