主 講 人：徐大川

講座時(shí)間：2020年12月4日15:00-16:00

講座地點(diǎn)：騰訊會(huì)議（會(huì)議號： 953 194 144； 密碼： 1204）

講座題目：Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques

講座內(nèi)容：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)

主講人簡介：徐大川，北京工業(yè)大學(xué)kaiyun開云官方網(wǎng)站運(yùn)籌學(xué)與控制論責(zé)任教授，數(shù)學(xué)/統(tǒng)計(jì)學(xué)博士生導(dǎo)師。北京工業(yè)大學(xué)區(qū)塊鏈研究中心副主任。2002年于中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院獲得博士學(xué)位。研究興趣包括：組合優(yōu)化、近似算法、機(jī)器學(xué)習(xí)等。中國運(yùn)籌學(xué)會(huì)數(shù)學(xué)規(guī)劃分會(huì)理事長，中國運(yùn)籌學(xué)會(huì)常務(wù)理事，北京運(yùn)籌學(xué)會(huì)副理事長。擔(dān)任AMC、APJOR、JORSC、運(yùn)籌與管理等期刊編委。在科學(xué)出版社出版學(xué)術(shù)專著《設(shè)施選址問題的近似算法》，在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等發(fā)表學(xué)術(shù)論文100余篇。

主辦：kaiyun開云官方網(wǎng)站信息與計(jì)算科學(xué)系