[Ml-stat-talks] IDeAS Seminar today at 3:00 pm - 110 Fine Hall
amits at math.Princeton.EDU
Thu Sep 18 09:20:47 EDT 2014
DATE: Thursday Sept. 18 , 2014
SEMINAR: IDeAS Seminar
PLACE: 110 Fine Hall
TIME: 3:00 pm
SPEAKER:Soledad Villar - University of Texas
TITLE: Integrality of clustering formulations
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
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).
Program in Applied & Computational Mathematics
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Ml-stat-talks