Southwest Jiaotong University School of Mathematics

信息与计算科学系

首页  >  学术科研  >  信息与计算科学系  >  正文

澳门新萄京手机游戏系列学术讲座:Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques

来源:   作者:     日期:2020-11-25 15:26:17   点击数:  

人:徐大川

 

讲座时间:202012415:00-16:00

 

讲座地点:腾讯会议(会议号: 953 194 144 密码: 1204

 

讲座题目:Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques

 

讲座内容: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+\veps$ to $9+\veps$. 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+\veps$ to $3+\veps$ for $k$-MedO, and from $274+\veps$ to $9+\veps$ for $k$-MeaO. (Joint work with Yishui Wang, Rolf H. Mohring, Chenchen Wu, and Dongmei Zhang)

 

主讲人简介:徐大川,北京工业大学新葡的京集团350vip运筹学与控制论责任教授,数学/统计学博士生导师。北京工业大学区块链研究中心副主任。2002年于中国科学院数学与系统科学研究院获得博士学位。研究兴趣包括:组合优化、近似算法、机器学习等。中国运筹学会数学规划分会理事长,中国运筹学会常务理事,北京运筹学会副理事长。担任AMCAPJORJORSC、运筹与管理等期刊编委。在科学出版社出版学术专著《设施选址问题的近似算法》,在Mathematical ProgrammingOperations ResearchINFORMS Journal on ComputingOmega AlgorithmicaJournal of Global OptimizationTheoretical Computer ScienceInformation Process Letters Journal of Combinatorial Optimization Operations Research Letters等发表学术论文100余篇。

 

主办:澳门新萄京手机游戏信息与计算科学系