bob买球-bob买球官方网站

学术信息

bob买球-bob买球官方网站

学术报告:Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques

  报告时候2021年4月15日(礼拜四)16:00

  报告地点:北辰校区理学院(西教五)416  

  报告标题题目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)  

  佳宾简介:徐大川,北京产业大学数学学院运筹学与节制论义务传授,数学/统计学博士生导师。北京产业大学区块链研讨中间副主任。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余篇。