报告题目：An approximation algorithm for the uniform capacitated $k$-means problem

报告人：徐大川教授

报告时间：2018年12月1日上午8:30

报告地点：数计学院2号楼309会议室

报告摘要：In this talk, we consider the uniform capacitated $k$-means problem (UC-$k$-means), an extension of the classical $k$-means problem in machine learning. In the UC-$k$-means, we are given a set of $n$ points $\\mathcal{D}$ in a $d$-dimensional space and an integer $k$. Each point in the $d$-dimensional space has an uniform capacity which is an upper bound of the number of points in $\\mathcal{D}$ that can be served by this point. Our goal is to find at most $k$ points in the space as centers to serve all the points in $\\mathcal{D}$ without violating the capacity constraint, such that the sum of the squared distance of each point in $\\mathcal{D}$ to its nearest center is minimized. Our main contribution is to propose a local search bi-criteria approximation algorithm for the UC-$k$-means, which violates the cardinality constraint.

报告人简介：北京工业大学数理学院副院长，北京科学与工程计算研究院副院长，北京工业大学区块链研究中心副主任，教授，博士生导师。2002年于中国科学院数学与系统科学研究院计算数学与科学工程计算研究所获得博士学位，2004年于中国科学院数学与系统科学研究院应用数学研究所博士后出站。曾访问斯坦福大学，加拿大新布伦瑞克大学，西蒙弗雷泽大学，香港中文大学等。研究兴趣包括：组合优化，近似算法，机器学习与优化，算法博弈论，鲁棒优化，供应链管理等。中国运筹学会数学规划分会副理事长/秘书长，北京运筹学会副理事长，中国运筹学会副秘书长/理事，中国数学会理事。《Applied Mathematics and Computation》、《Asia-Pacific Journal of Operational Research》、《Journal of the Operations Research Society of China》、《Statistics, Optimization and Information Computing》、《运筹与管理》编委，《Algorithmica》、《Journal of Combinatorial Optimization》、《运筹学学报》特约编委。曾获得中国运筹学会青年论文奖一等奖、中国运筹学会运筹新人奖。主持国家自然科学基金六项，国家自然科学基金重点项目子课题一项。在科学出版社出版学术专著《设施选址问题的近似算法》，在Mathematical Programming, Omega，INFORMS Journal on Computing，Algorithmica，Theoretical Computer Science，Journal of Combinatorial Optimization，Journal of Global Optimization，Information Process Letters，Operations Research Letters等发表学术论文100余篇。