Abstract: We consider the Correlation Clustering problem: given a collection of objects together with labels indicating which pairs of objects are "similar" and which are "dissimilar", we wish to cluster the objects so that "similar" objects lie in the same cluster and "dissimilar" objects lie in different clusters. Since a perfect clustering may not exist, the goal is to (approximately) minimize the number of "mistakes", that is, the number of similar pairs that end up in different clusters together with the number of dissimilar pairs that end up within clusters. We consider a weighted version of this problem and give an approximation algorithm that accepts a broader range of input weights than previous algorithms. We also study some variations on the basic problem.
Bio: Gregory Puleo is a Postdoctoral Research Associate at CSL, working in the research group of Olgica Milenkovic. In 2009 he earned a BS in Applied Mathematics at the Rochester Institute of Technology, and in 2014 he earned a PhD in Mathematics under the supervision of Douglas B. West. His research interests include extremal graph theory and optimization problems on graphs.