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

Dec, 2012

本文提出了一种新的近似k-means算法，采用多个随机空间分区树将数据预先组装成相邻点的组，并使用邻域信息构造每个簇的闭合形式，从而在分配步骤中只需考虑少量簇的候选项，证明该方法在聚类质量和效率方面优于现有的近似k-means算法。

Dec, 2013

本文提出了一种基于随机化的近似核 K-means 簇算法，其利用采样点与数据集中所有点之间的核相似性来近似聚类中心，实现了与传统低秩核近似聚类方案相比更好的聚类性能、更短的运行时间和更小的内存需求，最后利用集成聚类技术进一步提高算法性能。

Feb, 2014

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

Nov, 2018

本文提出了一种使用决策树对数据集进行聚类的算法，并探讨了该方法对 k-means 和 k-medians 目标函数的适用性。作者证明了常见的自顶向下决策树算法可能会导致成本任意大的聚类结果，但设计了一种有效的方法使用具有 k 个叶子的树生成可解释的聚类，并对于两个中心点的情况，仅需要一个阈值切割即可实现常数近似。

Feb, 2020

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

Jul, 2021

研究在可解释的k-中位数和k-均值问题中，提出了一种新的算法并分析了其竞争性和下界。

Jul, 2021

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

Jun, 2022

非监督学习中的聚类是一个基础问题，本研究介绍了一种简单的随机聚类算法，它在任意k下的期望运行时间为O(nnz(X) + nlogn)，并在K-means目标函数上实现了近似比例约为O(k^4)的算法，通过实验证明与现有方法相比，我们的聚类算法在运行时间和聚类质量之间有一个新的权衡。

Oct, 2023

在半随机图模型中，我们研究了平衡切割问题的精确性和时间复杂度，并且提出了第一个近似线性时间算法，以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间O(1)近似的方法。

Jun, 2024