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

Jun, 2022

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

Jun, 2021

本文提出了一种在社会公正聚类中的近似算法，这个问题包括了在一个度量空间中，给定一组点，每个点属于一个或多个组，为了同时满足所有组，需要找到一个 k - 中位数、k - 均值或者更一般意义上，l_p - 聚类，同时给出了强化的 LP 松弛，将其应用于近似算法和双标准近似算法，并取得了理论上的改进。

Mar, 2021

本文提出了一种基于局部搜索的算法，用于实现 $k$-median 和 $k$-means（以及任何使用 $\ell_p$ 范数的 $k$- 聚类），并从个体公平性的角度来考虑。我们的算法提供了一个逼近可行的 $k$- 聚类，其 $k$-median ($k$-means) 的成本与最优的 $k$- 聚类成本相比呈常数比例，并且我们的解决方案大约满足公平条件 (也在常数因子之内)。此外，我们还通过实证评估来补充我们的理论界限。

Feb, 2020

研究公平间距聚类问题，提供 O (1) 的近似算法在最多 k+2l 个中心中选择最小化聚类成本的一组中心，并仅在每个人口统计上最多违反 2 个加法项的上限。

Jun, 2023

本研究提出了一种实用的近似公平分解算法，几乎在线性时间内运行，可对结果聚类的平衡性进行更精细的控制。

Feb, 2019

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

Jun, 2021

本文提出了针对多个保护类的公平聚类方法，并且提出了一种松散的公平概念，在这种概念下，可以对所有经典聚类目标进行双标准常数因子近似，这是通过将任意现有不公平的（整数）解和公平的（分数）线性规划解结合起来实现的。

Nov, 2018

我们提出了一种可扩展的算法来解决由 Jung et al. 和 Mahabadi et al. 引入的个体公平（$p$, $k$）- 聚类问题。我们设计了首个快速局部搜索算法，具有～$O (nk^2)$ 的运行时间，并获得了（O (1), 6）的二对象近似解，然后我们通过实验证明了我们的算法不仅比以前的工作快得多，而且产生了更低成本的解决方案。

Feb, 2024

在这项研究中，我们研究了多样性感知聚类问题，其中数据点与多个属性相关联，导致交叉组。聚类解决方案需要确保从每个组中选择最少数量的聚类中心，同时最小化聚类目标，可以是 $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