可解释聚类的近似最紧算法
提出了一个算法，用于在 $k$-medians 目标和 $k$-means 目标下输出可解释的聚类，与最佳聚类最多相差 $O (\log^2 k)$ 和 $O (k\log^2 k)$ 的因子，算法时间为 $O (dk\log^2 k)$ 。
Jun, 2021
本文提出了一种使用决策树对数据集进行聚类的算法，并探讨了该方法对 k-means 和 k-medians 目标函数的适用性。作者证明了常见的自顶向下决策树算法可能会导致成本任意大的聚类结果，但设计了一种有效的方法使用具有 k 个叶子的树生成可解释的聚类，并对于两个中心点的情况，仅需要一个阈值切割即可实现常数近似。
Feb, 2020
介绍了一种可解释性聚类方法，算法通过应用决策树将数据划分为轴平行超平面聚类，使得聚类边界简单，同时保证聚类代价函数的可解释性约束，聚类的代价至多是比不考虑可解释性约束的情况最小代价增加 $k^{1-2/d}$ 倍，与其他方法的代价上界取最小值可得到 $k^{1-2/d} polylog (k)$ 倍，此为 $k,d ≥ 2$ 下的最优代价上界。
Jun, 2021
本文研究了基于 k-median 目标函数的聚类问题，提出了一种称为连续采样的简单但有效的采样技术，并使用该技术开发了一个可在 O（nk）时间内运行的算法来解决 k-median 问题。
Dec, 2012
该研究采用原始 - 对偶算法来解决 $k$-means 聚类问题，在满足集群数量限制的同时得到了 6.357 - 近似比的效果，并在欧几里得度量中解决了 $k$-median 的问题。
Dec, 2016
在这项研究中，我们研究了多样性感知聚类问题，其中数据点与多个属性相关联，导致交叉组。聚类解决方案需要确保从每个组中选择最少数量的聚类中心，同时最小化聚类目标，可以是 $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
本论文介绍了一个新的迭代舍入框架并用于许多聚类问题的近似算法，该算法可以大幅改善现有算法的近似比，并且通过前处理程序将几乎积分解转换为完全积分解。
Nov, 2017