BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/666
DTSTAMP:20230914T125933Z
SUMMARY:$D^2$ Sampling and the $k$-means Problem
DESCRIPTION:Speaker: Amit Kumar (Indian Institute of Technology\nDepartment
of Computer Science\nand Engineering\nHauz Khas\nNew Delhi 110016)\n\nAbs
tract: \nAbstract: Given a set of points $P$ in a $d$-dimensional Euclidea
n space\, the $k$-means clustering problem seeks to find a set $C$ of $k$
centers such that the sum over all points in $P$ of the square of the dist
ance to the closest center in $C$ is minimized. A natural random sampling
based heuristic for finding the $k$ centers is as follows -- pick the firs
t center uniformly at random from the set of points\, the next one with pr
obability proportional to the square of the distance from the first center
and so on. In this talk\, I will survey algorithms for the $k$-means prob
lem based on this random sampling technique. I will show that this idea ca
n be used to obtain fast PTAS for this problem. We extend this result to c
onstrained $k$-means clustering problems\, where there may be additional c
onstraints on valid clusterings of the input points (this is joint work
with Anup Bhattacharya and Ragesh Jaiswal).\n \n
URL:https://www.tcs.tifr.res.in/web/events/666
DTSTART;TZID=Asia/Kolkata:20160329T160000
DTEND;TZID=Asia/Kolkata:20160329T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR