Integrality of clustering formulations

Speaker: 
Soledad Villar - University of Texas
Date: 
Sep 18 2014 - 3:00pm
Event type: 
IDeAS
Room: 
110 Fine Hall
Abstract: 

When dealing with combinatoric NP-hard problems one can either find an efficient algorithm that works in every case but its solution is not optimal (that is the philosophy behind approximation algorithms). Or efficiently compute a probably optimal solution of the original problem under more restrictive hypothesis (which is the spirit of compressed sensing recovery guarantees).
In this talk we take the second approach applied to point cloud clustering problems; showing recovery conditions of the integral solution through their convex relaxations. We focus on two of the most common optimization problems for unsupervised clustering: k-means and k-medians clustering.
This talk is based on recent work with  P. Awasthi, A. S. Bandeira, M. Charikar, R. Krishnaswamy and R. Ward. (http://arxiv.org/abs/1408.4045).