Caltech Logo

Theory of Computing Seminar

Friday, June 3, 2016
12:00pm to 1:00pm
Add to Cal
Annenberg 213
Faster Algorithms for the Constrained k-means Problem
Ragesh Jaiswal, University of California, San Diego,

The classical center based clustering problems such as
k-means/median/center assume that the optimal clusters satisfy the
locality property that the points in the same cluster are close to each
other. A number of clustering problems arise in machine learning where
the optimal clusters do not follow such a locality property. For
instance, consider the r-gather clustering problem where there is an
additional constraint that each of the clusters should have at least r
points or the capacitated clustering problem where there is an upper
bound on the cluster sizes. In this work, we consider an extreme
generalization of such problems by assuming that the target clustering
is an arbitrary partition of the dataset. We show some interesting
results in this scenario.

(This is a joint work with Anup Bhattacharya (IIT Delhi) and Amit Kumar
(IIT Delhi))

Arxiv link:

For more information, please contact Thomas Vidick by email at [email protected].