报告题目：A local search approximation algorithm for a sum of squares k-facility location problem

报告摘要：In this talk, we introduce a sum of squares $k$-facility location problem (SOS-$k$-FLP) which is a common generalization of the classic $k$-means problem and the sum of squares facility location problem. In the SOS-$k$-FLP, we are given a client set $ X \subset \mathbb{R}^p$, a uniform center opening cost $f>0$, and an integer $k$. The goal is to open a center subset $F \subset \mathbb{R}^p$ with $ |F| \le k$ and to connect each client to the nearest open center such that the total cost (including center opening cost and the sum of squares of distances) is minimized. Using local search and scaling techniques, we offer a $(9+\sqrt{91}+\varepsilon)$-approximation algorithm for the SOS-$k$-FLP. Numerical tests indicate that a combination heuristic of our algorithm with iterated Lloyd's algorithm is efficient and effective in practice.

报告时间：2017年3月27日（周一）下午16:30-17:15

报告地点：长清湖校区C区236

欢迎老师和同学参加！

报告人简介：张冬梅，现为山东建筑大学计算机学院副教授。2012 年获山东大学计算机应用技术专业理学博士。主要研究兴趣为机器学习和信息检索，特别是文本情感分析。