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

Oct, 2018

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

Feb, 2015

本文介绍了一种新的 coresets 框架，可以在欧氏空间、翻倍度量、无小度量和一般的度量情况下同时改善 k - 中位数和 k - 均值聚类等问题的最优解的界限。

Apr, 2021

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

Jun, 2022

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

Apr, 2023

此论文介绍了一种可行的算法，用于从簇成员与簇中心之间的距离范数角度出发解决公平聚类问题，并对相应指标（如 bicriteria）进行了优化；同时，提供了一种基于模类约束的距离范数成本设施位置 16^p - 近似算法，并将借鉴此算法，将个体公平聚类转化为更一般如群体公平聚类的解法。

Jun, 2021

本研究提出了一种统一的两阶段重要性采样框架，可构建 (k,z) 聚类问题的 ε-coreset。该算法依赖于将两个形状拟合问题连接起来的新的降维技术，绕过了之前的构造时间和核心集大小的限制，并提供了一个核心集的下界。

Apr, 2020

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

Dec, 2018

本文提出了一种在社会公正聚类中的近似算法，这个问题包括了在一个度量空间中，给定一组点，每个点属于一个或多个组，为了同时满足所有组，需要找到一个 k - 中位数、k - 均值或者更一般意义上，l_p - 聚类，同时给出了强化的 LP 松弛，将其应用于近似算法和双标准近似算法，并取得了理论上的改进。

Mar, 2021

在这项研究中，我们研究了多样性感知聚类问题，其中数据点与多个属性相关联，导致交叉组。聚类解决方案需要确保从每个组中选择最少数量的聚类中心，同时最小化聚类目标，可以是 $k$-median、$k$-means 或 $k$-supplier。我们提出了参数化逼近算法，逼近比例分别为 $1+ rac {2}{e}$、$1+rac {8}{e}$ 和 $3$，用于多样性感知 $k$-median、多样性感知 $k$-means 和多样性感知 $k$-supplier。这些逼近比例在假设 Gap-ETH 和 FPT $ eq$ W [2] 的情况下是紧密的。对于公平 $k$-median 和公平 $k$-means 与不相交设施组，我们分别提出了参数化逼近算法，逼近比例为 $1+rac {2}{e}$ 和 $1+rac {8}{e}$。对于公平 $k$-supplier 与不相交设施组，我们提出了一个多项式时间逼近算法，其因子为 $3$，改进了先前已知的逼近比例因子为 $5$。

Jan, 2024