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.