基于平方和范数的 $k$-means 聚类的凸松弛算法及其学习算法，能够学习高斯混合物的均值。

Nov, 2017

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

Dec, 2016

运用线性规划和局部搜索算法解决在数据聚类问题中，$\ell_p$-range 目标下的个体公平问题。通过修改 LP 理论和结合局部搜索算法实践，实现更优算法，并在实验中展现了出众的表现。

Jun, 2021

通过对 Semidefinite Programming（SDP）放松的最大似然估计进行研究，本文论证了 SDP 放松技术在社区检测中的可行性和通用性。

Feb, 2015

给定一组点，聚类是找到一个点集合的分区，使分配给一个点的中心尽可能接近。对于中心为点的目标，我们显示了一个收敛速度为 O (sqrt (k/n)) 的收敛界限。对于中心为 j 维子空间的子空间聚类，我们显示了一个收敛速度为 O (sqrt ((kj^2)/n)) 的收敛界限。对于广义 $k$-means 的投影聚类特例，我们证明了一个收敛速度为 Omega (sqrt ((kj)/n)) 的必要界限。

Oct, 2023

研究了通过 lp 最小化距离来恢复高维数据集中 K 个线性子空间的问题，其中数据来自于一个混合分布，包含 K+1 个组成部分，包括一个在球体上均匀分布的 outliers 和 K 个在球体上限制的直线子空间，以及解决了在这个问题中 lp 最小化是非凸的问题，结果表明，如果 0＜p≤1，则 lp 最小化可以精确地恢复所有的线性子空间和 l0 最佳的子空间，而对于 K>1 和 p>1，无法恢复或近似恢复所有线性子空间和最佳的 l0 子空间。

Feb, 2010

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

Feb, 2015

研究了混合有界协方差分布的聚类问题，使用细粒度分离假设；提供了用于聚类任务的多项式时间算法，并指出了在细粒度均值分离假设下精确聚类是信息理论上不可能的；引入了聚类细化的概念并证明了可以高效计算出样本的精确聚类细化；此外，根据先前工作中的一个变体条件，我们的算法输出准确聚类，甚至适用于一般权重的混合物。

Dec, 2023

探讨如何将具有某些限制的聚类问题的近似算法转化为更符合隐私约束的近似算法，并结合隐私与其他约束条件。

Feb, 2018

本文旨在通过改进 Kumar 和 Kannan [2010] 的分离条件，探讨聚类混合分布。本文通过较弱的分离条件和接近度条件，得出了具有低误差和低 k - 均值成本的聚类结果，在某些情况下能够改进高斯模型的分离结果。

Jun, 2012