DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2010.2486

Online Correlation Clustering

Authors: Claire Mathieu, Ocan Sankur, and Warren Schudy

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

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 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.

Cite as

Claire Mathieu, Ocan Sankur, and Warren Schudy. Online Correlation Clustering. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 573-584, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{mathieu_et_al:LIPIcs.STACS.2010.2486,
  author =	{Mathieu, Claire and Sankur, Ocan and Schudy, Warren},
  title =	{{Online Correlation Clustering}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{573--584},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2486},
  URN =		{urn:nbn:de:0030-drops-24862},
  doi =		{10.4230/LIPIcs.STACS.2010.2486},
  annote =	{Keywords: Correlation clustering, online algorithms}
}

Search Results

Documents authored by Schudy, Warren

Online Correlation Clustering

Abstract

Cite as

Thanks for your feedback!

Could not send message