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