本研究采用图谱分析的方法，证明了欧几里得 k-means 问题的近似难度对于所有的 k 和 d 都是 NP 难的，同时发现当前最佳难度结果可以被推广到三角免费图中。

Feb, 2015

研究了一种叫做有序 k - 中位数的问题，并提出了一种（18+ε）- 近似算法，该算法结合了广义松弛和原始对偶模式，并使用了 Aouad 和 Segev 的枚举过程。对于特殊情况的 {0,1} 权重，提出了一种新颖的规约方法，并得到了一个干净简洁的（8.5+ε）- 近似算法。

Nov, 2017

探讨如何将具有某些限制的聚类问题的近似算法转化为更符合隐私约束的近似算法，并结合隐私与其他约束条件。

Feb, 2018

本文介绍了 Robust k-z 聚类和其在度量空间、算法公平性、欧几里得空间和 FPT 近似等领域的应用，提出了相应的算法，其中在特殊的欧几里得空间中得到了较好的近似结果。

May, 2023

研究了 k-means 问题在 Euclidean 空间中寻找 k 个中心使得所有点到离它们最近中心的距离平方和最小，证明了该问题的近似难度是 NP-hard，并且提出了最小近似系数 1.0013。

Sep, 2015

该研究提供了一种在输入稳定条件下解决对称和非对称 $k$-center 问题的算法，并且这种算法在输入距离 2 - 扰动稳定时可以在最劣情况下保证聚类近似算法的最优解。

May, 2015

本研究对含 m 个群体的社会公平 (l_p, k)- 聚类问题的近似算法进行研究，其中特殊情况包括社会公平 k - 中心 (p=1) 和社会公平 k - 均值 (p=2) 问题。研究分别给出了多项式时间和两种不同的 (n^{2^{O (p)} m^2} 和 k^m poly (n)) 的近似算法，并探讨了这些算法与现有算法的比较。

Jun, 2022

本文证明了当度量空间中没有 Steiner 点时，对于任何以中心为基础的聚类目标函数（例如 k - 中位数，k - 均值和 k - 中心），我们可以有效地找到最优的聚类，假设仅稳定于基础度量的 3 倍扰动，对于一般的度量，稳定性因子为 2 + 根号 3 扰动，我们还在相关条件下提出了 NP 困难性结果。

Sep, 2010

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

Mar, 2016

在分布式环境中，对 $k$-center/median/means 聚类与 outliers 问题 (或 $(k, z)$-center/median/means 问题) 进行研究，提出了一种改进算法，能够更好地解决 communication costs 线性依赖于 outliers 数量的问题。

Oct, 2018