报告题目：Centralized and Distributed Algorithms for Clustering with Outliers Problems
In this talk, I will present two of my recent papers on clustering with outliers problems. The first paper gives a novel iterative rounding framework that leads to 0(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 0(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. The second paper considers the k-center/median/means clustering with outliers problems in the distributed setting. Most previous distributed algorithms have their communication costs linearly depending on z, the number of outliers. Recently (Guha et al, SPAA 2017] overcame this dependence issue by considering bi-criteria approximation algorithms that output solutions with 2z outliers. For the case where z is large, the extra z outliers discarded by the algorithms might be too large, considering that the data gathering process might be costly. In this paper, we improve the number of outliers to the best possible (1+\epsilon)z, while maintaining the 0(1)-approximation ratio and independence of communication cost on z. Implementation of the our algorithm for k-center with outliers shows that it outperforms many previous algorithms, both in terms of the communication cost and quality of the output solution.
Dr.Li is an assistant professor at the department of computer science and engineering at the University at Buffalo since 2015. Before joining the university, he was a research assistant professor at Toyota Technological Institute at Chicago. Dr.Li received his Ph.D. in 2013 from the Department of Computer Science at Princeton University, supervised by Prof. Moses Charikar. He received his Bachelor’s degree in 2008 from the Department of Computer Science and Technology at Tsinghua University, where he was also a student of Andrew Chih-Chi Yao’s Special Pilot Class. Dr.Li’s main research focus is on designing efficient approximation algorithms for classic NP-hard combinatorial problems and has published more than a dozen of research papers on prestigious TCS conferences such as STOC, FOCS and SODA.