Computer Science – Data Structures and Algorithms
Scientific paper
2010-01-06
Computer Science
Data Structures and Algorithms
12 pages, 1 figure
Scientific paper
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.
Mathieu Claire
Sankur Ocan
Schudy Warren
No associations
LandOfFree
Online Correlation Clustering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Online Correlation Clustering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Correlation Clustering will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-164435