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