Abstract

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.

Time

8月15日（周三）14:00-15:00

Speaker

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.

Venue

信息管理与工程学院  602会议室

上海财经大学

上海市杨浦区武东路100号