学术信息

当前位置: > 学术信息 >

关于举办《A local search approximation algorithm for the k-means problem with penalties》学术报告的通知

发布日期:2017-06-07 10:00      来源:未知      点击:
报 告 人: 徐大川教授(北京工业大学数理学院博士生导师)
报告时间: 2017年6月11日(周日) : 10:30-11:30
地    点: 理学院学院报告厅(1号教学楼A404)
报告题目: A local search approximation algorithm for the k-means problem with penalties
   : In this talk, we study the k-means problem with (nonuniform) penalties (k-MPWP) which is a natural generalization of the classic k-means problem. In the k-MPWP, we are given an n-client set $ \mathcal{D}\subset\mathbb{R}^d$, a penalty cost $p_j>0$ for each $j \in\mathcal{D}$, and an integer k<=n. The goal is to open a center subset $F\subset\mathbb{R}^d$ with $|F| \le k$ and to choose a client subset $P \subseteq\mathcal{D}$ as the penalized client set such that the total cost (including the sum of squares of distance for each client in $\mathcal{D} \setminus P$ to the nearest open center and the sum of penalty cost for each client in P) is minimized. We offer a local search $(81+ \varepsilon)$-approximation algorithm for the k-MPWP by using single-swap operation. We further improve the above approximation ratio to $(25+\varepsilon )$ by using multi-swap operation. (Joint work with Dongmei Zhang, Chunlin Hao, Chenchen Wu, and Zhenning Zhang)
徐大川教授简介:北京工业大学数理学院教授,博士生导师,科研副院长。2002年于中国科学院数学与系统科学研究院获得博士学位。曾访问斯坦福大学,加拿大新布伦瑞克大学,西蒙弗雷泽大学,香港中文大学等。研究兴趣包括:组合优化,近似算法,算法博弈论,鲁棒优化,供应链管理等。中国运筹学会数学规划分会副理事长/秘书长,中国运筹学会理事,北京运筹学会常务理事,中国数学会理事。《运筹与管理》和《Applied Mathematics and Computation》编委,《运筹学学报》、《Asia-Pacific Journal of Operational Research》、《Algorithmica》、《Theoretical Computer Science》、《Journal of Combinatorial Optimization》特约编委。主持国家自然科学基金四项、国家自然科学基金重点项目子课题1项。在科学出版社出版学术专著《设施选址问题的近似算法》,在Omega,INFORMS Journal on Computing,Algorithmica,Theoretical Computer Science,Journal of Combinatorial Optimization,Journal of Global Optimization,Operations Research Letters等发表学术论文80余篇。
                                                          沈航科协
                                                          2017/6/7