Timezone: »

 
Poster
Robust Online Correlation Clustering
Silvio Lattanzi · Benjamin Moseley · Sergei Vassilvitskii · Yuyan Wang · Rudy Zhou

Fri Dec 10 08:30 AM -- 10:00 AM (PST) @
in Poster Session 8 »

In correlation clustering we are given a set of points along with recommendations whether each pair of points should be placed in the same cluster or into separate clusters. The goal cluster the points to minimize disagreements from the recommendations. We study the correlation clustering problem in the online setting., where points arrive one at a time, and upon arrival the algorithm must make an irrevocable cluster assignment decision. While the online version is natural, there is a simple lower bound that rules out any algorithm with a non-trivial competitive ratio. In this work we go beyond worst case analysis, and show that the celebrated Pivot algorithm performs well when given access to a small number of random samples from the input. Moreover, we prove that Pivot is robust to additional adversarial perturbations of the sample set in this setting. We conclude with an empirical analysis validating our theoretical findings.

Keywords: Clustering

Author Information

Silvio Lattanzi (Google Research)
Benjamin Moseley (Carnegie Mellon University)
Sergei Vassilvitskii (Google)
Yuyan Wang (Carnegie Mellon University)
Rudy Zhou (CMU, Carnegie Mellon University)

More from the Same Authors