本文研究了基于k-median目标函数的聚类问题，提出了一种称为连续采样的简单但有效的采样技术，并使用该技术开发了一个可在O（nk）时间内运行的算法来解决k-median问题。

Dec, 2012

本文提出了一种双树算法，用于加速k-means聚类算法在大规模K簇和数据集下进行迭代，在使用了覆盖树后，该算法的单次迭代运行时间为O(N + k log k)，并且在实践中表现得很好。

Jan, 2016

我们提出了一种新颖的加速精确k-means算法，在18个实验中比现有低维算法更优秀，速度快了最多三倍。 我们还通过更好地估计用于减少距离计算次数的距离界限，对现有最先进的加速精确k-means算法进行了总体改进，在44个实验中实现了速度提升，最高达到1.8倍。最后，我们提出了标准方法的简化版本，并表明它们在59个实验中比其全面版本更快。

Feb, 2016

使用局部搜索启发式策略，本文证明了在任何固定维度的欧几里得空间中，k-means问题均可提供 PTAS。

Mar, 2016

通过投影到随机的O(log(k/ ε) / ε²)维子空间上，可以近似保持欧几里得k-means或k-medians聚类的最优解成本，并且适用于任何满足温和的子高斯尾条件的维度缩减映射，其维数几乎是最优的。此外，该结果适用于所有权重的欧几里得k-聚类。

Nov, 2018

在本研究中，我们提出了Kernel Ridge Regression (KRR)和Kernel K-means聚类(KKMC)中所需的核函数评估数量的严格下限，并且通过有效的统计维度，我们的KRR结果解决了一个关于采样复杂度的开放性问题。此外，对于输入数据为高斯混合模型的情况，我们提供了一种超越了上述下限的KKMC算法。

May, 2019

本文研究了Ward方法在分层k均值问题中的应用，通过对完全链接的算法进行分析，发现当最优k聚类具有良好分离性时，Ward方法可以计算出k-均值目标函数的2-近似解，并证明了当最优聚类满足平衡条件时，Ward方法完全恢复最优解，并且我们证明了一维数据集的Ward聚类可以实现O(1)的近似解。

Jul, 2019

介绍了一种新的差分隐私算法，该算法通过将问题转化为基于网格的最大覆盖问题的一系列实例，实现了较低的加性误差并保持恒定的乘性误差，在$k$-means聚类问题上取得了更好的实验效果。

Sep, 2020

给定一组点，聚类是找到一个点集合的分区，使分配给一个点的中心尽可能接近。对于中心为点的目标，我们显示了一个收敛速度为O(sqrt(k/n))的收敛界限。对于中心为j维子空间的子空间聚类，我们显示了一个收敛速度为O(sqrt((kj^2)/n))的收敛界限。对于广义$k$-means的投影聚类特例，我们证明了一个收敛速度为Omega(sqrt((kj)/n))的必要界限。

Oct, 2023

本文介绍了一种几乎线性时间算法，用于计算聚类问题的常数因子近似解。

Jul, 2024