MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Faster Algorithms for the Constrained k-means Problem

Ragesh Jaiswal
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Tuesday, 16 June 2015
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

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 generalisation 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 joint work with Anup Bhattacharya (IIT Delhi) and Amit Kumar (IIT Delhi).

(arXiv link: http://arxiv.org/abs/1504.02564)

Contact

Andreas Wiese
--email hidden
passcode not visible
logged in users only

Andreas Wiese, 05/27/2015 16:03 -- Created document.