Iterative rounding for k-median and k-means clustering with outliers (Shi Li)


In this talk I will present a novel iterative rounding framework that leads to O(1)-approximation algorithms for k-median and k-means with outliers problem. The result for k-median with outliers greatly improves upon the large implicit constant approximation ratio of [Chen SODA 2008], and the result for k-means with outliers is the first O(1)-approximation for this problem. The iterative algorithm framework is very versatile: It can be used to give improved results for many other clustering problems.
Based on joint work with Ravishankar Krishnaswamy​ and Sai Sandeep.


2018-08-15   14:00 ~ 15:00   


Shi Li, University at Buffalo


Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics