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

Mar, 2016

该研究采用原始 - 对偶算法来解决 $k$-means 聚类问题，在满足集群数量限制的同时得到了 6.357 - 近似比的效果，并在欧几里得度量中解决了 $k$-median 的问题。

Dec, 2016

本文研究了一个最近提出的可解释聚类框架，专注于 k-medians 和 k-means 问题，并提供了近似算法和上下界。

Jul, 2021

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

May, 2023

该研究提出了一种新颖的近似算法，在 K - 中位数中实现了 1+sqrt（3）+ epsilon 的近似保证，该方法基于两个组件，第一个是关于伪近似算法的，第二个是关于 K 个设施的。

Nov, 2012

本文研究了度量实例的本地搜索算法，针对设备位置问题：无容量设备位置问题（UFL），以及 $k$-median，$k$-center 和 $k$-means 的无容量版本。

Sep, 2008

本研究提出了基于同类簇查询与有噪音答案的方法，解决了离群点存在情况下的近似 K-means 聚类优化问题，证明了在一定条件下可以以大概率获得最优潜在解的 (1+ε）近似解，并且比目前已知的方法减少了同类簇查询数量。这种方法也推广到了控制噪音、离群点的场景中，同时在人造数据集和真实数据集上进行了测试。

Jun, 2018

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

Jun, 2022

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

Feb, 2015

提供了一种基于 LP-rounding 的近似算法来解决有序 k-Median 问题，并探讨了包括权重和距离分配方法在内的多种算法来处理该问题。

Nov, 2017