交互式聚类的本地算法
本文研究在实际应用中，哪些加性扰动稳定性的实例可以设计有效算法，并证明它们能找到最优聚类。我们提出了一种稳定性定义，并设计了算法以证明稳定实例的最优聚类。当实例具有一定的分离性时，我们显示出一种具有证明保证的鲁棒算法，也能容忍异常值。通过研究真实数据集的稳定性，我们补充了这些结果，并展示了我们的算法在这些基准数据集上的表现。
Dec, 2017
本文研究了大规模图的本地算法设计并提出了一种本地聚类算法，该算法可在几乎线性的时间内找到较好的簇，并基于该聚类算法提出了一种划分算法，进而设计了求解对称对角占优矩阵中线性系统的近线性算法，还提出了其他相关结果。
Sep, 2008
本文研究了个体偏好稳定性（IP Stability），该概念捕捉了聚类中的个体公平性和稳定性。在这个设置中，如果每个数据点到其簇的平均距离不超过其到其他簇的平均距离的 α 倍，那么聚类就是 α-IP 稳定的。本文研究了个体偏好稳定聚类的自然局部搜索算法，我们的分析证实了该算法具有 O (log n)-IP 稳定性保证，其中 n 是输入中点的数量。此外，通过改进局部搜索方法，我们展示了该算法运行时间几乎是线性的，即约为 O (nk)。
Mar, 2024
本文研究了在输入稳定性假设下的差分隐私聚类问题，提出了一种简单的算法，分析了其在 Wasserstein 距离和 k-means 代价等方面的效用，可直接应用于 “好” 的 k - 中位数实例和本地模型的差分隐私。
Jun, 2021
本文提出了一种算法，用于在差分隐私（DP）的一轮（也称非交互式）本地模型中进行 k 均值聚类，该算法实现的逼近比接近于最佳非私有逼近算法，改进了以前已知的仅保证大（常数）逼近比率的算法。此外，这是第一个仅需要一轮本地 DP 模型通信的 k 均值常数逼近算法，积极地解决了 Stemmer（SODA 2020）提出的一个开放性问题。我们的算法框架非常灵活；我们通过展示在（一轮）洗牌 DP 模型中也会产生类似于最优解的逼近算法来证明这一点。
Apr, 2021
本文提出了一种新的鲁棒的自下而上聚类算法，并展示了在满足一定自然属性且传统算法失效的情况下，该算法可以被用来进行准确的聚类。同时，该算法也被适用于归纳设置，并在合成数据和真实数据集上的实验表明，在存在噪音时，与其他分层算法相比，该算法可以获得更好的表现。
Jan, 2014