信息門戶
ENGLISH
舊版回顧
當前位置: 首頁>>學術講座>>正文

關于北京工業大學徐大川教授學術報告的通知

发布时间:2021-04-13 作者:  来源: 阅读量:[]

報告題目:Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques

報告人:徐大川 教授

報告時間:4月16日15:00-16:00

報告地點:6號教學樓303室

報告簡介:

In this talk, we consider two types of robust models of the k-median/k-means problems: the outlier-version (k-MedO/k-MeaO) and the penalty-version (k-MedP /k-MeaP), in which we can mark some points as outliers and discard them. In k-MedO /k-MeaO, the number of outliers is bounded by a given integer. In k-MedO/k-MeaO, we do not bound the number of outliers, but each outlier will incur a penalty cost. We develop a new technique to analyze the approximation ratio of local search algorithms for these two problems by introducing an adapted cluster that can capture useful information about outliers in the local and the global optimal solution. For k-MeaP, we improve the best known approximation ratio based on local search from 25+\epsilon to 9+\epsilon. For k-MedP, we obtain the best known approximation ratio. For k-MedO/k-MeaO, there exists only two bi-criteria approximation algorithms based on local search. One violates the outlier constraint (the constraint on the number of outliers), while the other violates the cardinality constraint (the constraint on the number of clusters). We consider the former algorithm and improve its approximation ratios from 17+\epsilon to 3+\epsilon for k-MedO, and from 274+\epsilon to 9+\epsilon for k-MeaO. (Joint work with Yishui Wang, Rolf H. Mohring, Chenchen Wu, and Dongmei Zhang)

報告人簡介:

徐大川,北京工业大学数学学院运筹学与控制论责任教授,数学/统计学博士生导师。北京工业大学区块链研究中心副主任。2002年于中国科学院数学与系统科學研究院获得博士学位。研究兴趣包括:组合优化、近似算法、机器学习等。中国运筹学会数学规划分会理事长,中国运筹学会常务理事,北京运筹学会副理事长。担任AMC、APJOR、JORSC、运筹与管理等期刊编委。在科学出版社出版学术专著《设施选址问题的近似算法》,在Mathematical Programming,Operations Research,INFORMS Journal on Computing,Omega,Algorithmica,Journal of Global Optimization,Theoretical Computer Science,Information Process Letters,Journal of Combinatorial Optimization,Operations Research Letters等期刊和AAAI, ICDCS,COCOON等会议发表学术论文100余篇。


理學院

2021年4月13日

上一條:關于《構建區塊鏈互聯生態的思考與實踐》學術報告通知
下一條:關于開展青年學者沙龍活動的通知

關閉

相關鏈接
 
地址:天津市西青区宾水西道391号 邮编:300384  
電話:0086-22-60215678  傳真:0086-22-60215555  
本科招生電話:0086-22-60216795
ICP備案號:津ICP備11001169號-1|津教備0064號