首页
学院新闻
学院公告
学术信息
就业信息

美国纽约州立大学(布法罗)栗师博士学术报告

来源: 点击: 时间: 2018年08月03日 17:19

报告题目Centralized and Distributed Algorithms for Clustering with Outliers Problems

报告时间:201886日上午11:00

报告地点:校本部升华后楼215

报告简介:

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.

 


返回首页

上一条:德国杜伊斯堡-埃森大学Steven Ding教授学术报告

下一条:中南大学名师名家论坛---加拿大西安大略大学Dr.Shuo Li教授学术报告