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.
Document type :
Conference papers
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.573-584, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées


https://hal.inria.fr/inria-00455771
Contributor : Publications Loria <>
Submitted on : Thursday, February 11, 2010 - 10:40:35 AM
Last modification on : Wednesday, September 28, 2016 - 3:51:53 PM
Document(s) archivé(s) le : Friday, June 18, 2010 - 5:47:35 PM

File

mathieu.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455771, version 1

Collections

Citation

Claire Mathieu, Ocan Sankur, Warren Schudy. Online Correlation Clustering. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.573-584, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00455771>

Share

Metrics

Record views

155

Document downloads

130