ARC Colloquium: Ravi Kannan, Microsoft Research, India

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.

Event Details

Date/Time:

  • Monday, September 17, 2012
    1:00 pm
Location: Klaus 1116

For More Information Contact