带惩罚的相同容量k-均值问题的局部搜索算法

经典$k$-均值问题是一类应用广泛的聚类问题，它是指给定$\mathbb{R}^d$中观测点集合$D$和整数$k$，目的是在空间中寻找$k$个点作为中心集合$S$，使得集合$D$中的每个观测点到$S$中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典$k$-均值问题有很多推广，本文研究的带惩罚的相同容量$k$-均值问题就是其中之一。与经典$k$-均值问题相比，惩罚性质是指每个观测点都给定惩罚费用，当某个观测点到最近中心的距离大于惩罚费用时，其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方，相同容量约束要求每个中心至多连接$U$个观测点。针对这种问题，我们设计了局部搜索算法，该算法在至多选取$（3+\alpha）k$个中心的情况下，可以达到$\beta$-近似，其中，参数$\alpha>34$，$\beta>\frac{\alpha+34}{\alpha-34}$。

A local search analysis for the uniform capacitated $k$-means problem with penalty

The classical $k$-means problem has numerous application in the real world. Given a set of data points $D$ in ${\mathbb R}^d$ and an integer $k$, the aim is to select $k$ points in ${\mathbb R}^d$ as a central set $S$, such that the sum of the square of the distance between each point and its closest center in $S$ is minimized. It is a NP-hard problem and has many generalizations, one of which is the uniform capacitated $k$-means problem with penalty. Compared with the classical $k$-means problem, the penalty implies that each data point has a penalty cost, when the distance from some data points to their nearest center is greater than the penalty cost, they contribute the penalty cost. As for the uniform capacity, it suggests that each center is connected at most $U$ times. For this variant problem, we design a local search algorithm which selects at most $(3+\alpha)k$ centers and reaches $\beta$-approximate, where $\alpha>34$, $\beta>\frac{\alpha+34}{\alpha-34}$.