在一项研究中，我们引入了个体偏好稳定性（IP 稳定性），作为一种受稳定性和公平性约束启发的自然聚类目标。我们证明了对于一般度量，总存在一个 O (1)-IP 稳定的聚类算法，并且还介绍了 IP 稳定性在平均距离以及簇内和簇间最大最小距离情况下的推广。

Sep, 2023

本文研究了个体偏好稳定性（IP Stability），该概念捕捉了聚类中的个体公平性和稳定性。在这个设置中，如果每个数据点到其簇的平均距离不超过其到其他簇的平均距离的 α 倍，那么聚类就是 α-IP 稳定的。本文研究了个体偏好稳定聚类的自然局部搜索算法，我们的分析证实了该算法具有 O (log n)-IP 稳定性保证，其中 n 是输入中点的数量。此外，通过改进局部搜索方法，我们展示了该算法运行时间几乎是线性的，即约为 O (nk)。

Mar, 2024

本文证明了当度量空间中没有 Steiner 点时，对于任何以中心为基础的聚类目标函数（例如 k - 中位数，k - 均值和 k - 中心），我们可以有效地找到最优的聚类，假设仅稳定于基础度量的 3 倍扰动，对于一般的度量，稳定性因子为 2 + 根号 3 扰动，我们还在相关条件下提出了 NP 困难性结果。

Sep, 2010

本文研究在实际应用中，哪些加性扰动稳定性的实例可以设计有效算法，并证明它们能找到最优聚类。我们提出了一种稳定性定义，并设计了算法以证明稳定实例的最优聚类。当实例具有一定的分离性时，我们显示出一种具有证明保证的鲁棒算法，也能容忍异常值。通过研究真实数据集的稳定性，我们补充了这些结果，并展示了我们的算法在这些基准数据集上的表现。

Dec, 2017

本文研究了基于稳定性假设的交互式聚类算法设计，算法开始于任意初始聚类，只进行每步的局部更改；我们证明在这种约束条件下，仍然可以设计出具有可证明高效和准确聚类能力的算法，并在真实数据上进行了实证。

Dec, 2013

本文研究了在输入稳定性假设下的差分隐私聚类问题，提出了一种简单的算法，分析了其在 Wasserstein 距离和 k-means 代价等方面的效用，可直接应用于 “好” 的 k - 中位数实例和本地模型的差分隐私。

Jun, 2021

本文研究公平聚类问题并提出了采用 f - 散度测量统计相似度，以确保相似的个体得到类似的对待，该方案保证了群体公平性与个人公平性。在 $p$- 范目标的约束下，我们提供了可证明的近似保证聚类算法。同时，我们还考虑了群体公正和个人公正在受保护群体内的实现条件，并证明了个人公平性是群体公平性的必要条件。实验证明了这种方法的有效性。

Jun, 2020

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

Jun, 2021

本文考虑了 Bilu 和 Linial（2010）提出的模型，研究了最佳聚类不发生变化的问题，我们发现即使问题是 NP 困难的，有时候也可能获得有效算法，这些算法对于特定的多项式扰动是鲁棒的。同时，我们证明了该区间内的乘法鲁棒性参数可能太强，以至于聚类问题变得微不足道，只有一个较窄的区间是有趣的。

Jul, 2011

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

Jun, 2021