Speaker:
Qilong Feng(Central South University)
Time:
- 11:00 (Time in Beijing)
- 15:00 (Time in Auckland)
- June 17, 2021 (Thursday)
Venue:
Baixue Tang, UESTC Library
Abstract:
Designing approximation algorithms for the clustering problem remains an active area of research. However, these algorithms can significantly deteriorate their performance in real-world applications. The major reason is that real-world applications often involve additional constraints (such as capacities and lower bounds of facilities) on the input data. In this talk, we first introduce several polynomial-time algorithms with improved approximation ratios for constrained clustering problems such as prize-collecting red-blue median, priority k-median, and lower-bounded k-median. Secondly, we introduce a unified framework for designing FPT(k)-time approximation algorithms in the presence of additional constraints. This framework yields algorithms with improved approximation ratios for the problems of capacitated clustering, lower-bounded clustering, fault-tolerant clustering, clustering with service installation costs, and priority clustering.
Speaker Bio:
冯启龙，中南大学计算机学院教授，博士生导师。2008年9月至2010年4月，公派留学美国Texas A&M University。一直从事于计算机算法优化、机器学习算法优化等方面的研究。近年来，主持国家自然科学基金面上项目2项、国家自然科学基金青年基金项目1项。担任FCS编委、国际会议TAMC 2020大会主席。