Fall 2018

Monte Carlo Approximation Certificates for K-Means Clustering

Wednesday, November 28th, 2018 4:00 pm4:40 pm

Add to Calendar


Dustin Mixon (Ohio State University)

Efficient algorithms for k-means clustering frequently converge to suboptimal partitions, and given a partition, it is difficult to detect k-means optimality. We discuss an a posteriori certifier of approximate optimality for k-means clustering based on Peng and Wei's semidefinite relaxation of k-means.