*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: k-MEANS REVISITED
Abstract:
In many applications, fairly fast clustering algorithms seem to yield the desired solution. Theoretically, two types of assumptions lead to provably fast algorithms for clustering:
(i) stochastic (mixture) models of data and (ii) uniqueness of optimal solution even under perturbations of data. We show that under an assumption weaker than either of these, Lloyd's (k-means) algorithm converges to the correct solution. We apply the result to the planted clique problem.
Joint work with Amit Kumar.
