针对度量空间中的经典设施定位、$k$- 中位数和 $k$- 均值问题，我们提供了近线性时间的逼近方案，并展示了针对各种变型问题的技术扩展。

Dec, 2018

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

Feb, 2015

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

Sep, 2008

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

Dec, 2016

通过考虑更大和更复杂的局部搜索邻域，我们的算法实现了 9 + ε 的逼近比，这是局部搜索的最佳可能性，并且在几个数据集上显著改进了 Lattanzi 和 Sohler（ICML 2019）的方法。

Sep, 2023

本文提出了一种简洁的 EPAS 算法，它能够适用于多种簇集聚类问题，并且包括多种测度空间，算法的关键是新概念限制了标准封闭维数的标准，从而为聚类问题提供了更多可能性。

Apr, 2023

我们提出了一种可扩展的算法来解决由 Jung et al. 和 Mahabadi et al. 引入的个体公平（$p$, $k$）- 聚类问题。我们设计了首个快速局部搜索算法，具有～$O (nk^2)$ 的运行时间，并获得了（O (1), 6）的二对象近似解，然后我们通过实验证明了我们的算法不仅比以前的工作快得多，而且产生了更低成本的解决方案。

Feb, 2024

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

May, 2023

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

Sep, 2015

本文提出了一种算法，用于在差分隐私（DP）的一轮（也称非交互式）本地模型中进行 k 均值聚类，该算法实现的逼近比接近于最佳非私有逼近算法，改进了以前已知的仅保证大（常数）逼近比率的算法。此外，这是第一个仅需要一轮本地 DP 模型通信的 k 均值常数逼近算法，积极地解决了 Stemmer（SODA 2020）提出的一个开放性问题。我们的算法框架非常灵活；我们通过展示在（一轮）洗牌 DP 模型中也会产生类似于最优解的逼近算法来证明这一点。

Apr, 2021