KFC:$k$- 中心公平聚类的可扩展近似算法
本文提出了针对多个保护类的公平聚类方法,并且提出了一种松散的公平概念,在这种概念下,可以对所有经典聚类目标进行双标准常数因子近似,这是通过将任意现有不公平的(整数)解和公平的(分数)线性规划解结合起来实现的。
Nov, 2018
我们提出了一种可扩展的算法来解决由 Jung et al. 和 Mahabadi et al. 引入的个体公平($p$, $k$)- 聚类问题。我们设计了首个快速局部搜索算法,具有~$O (nk^2)$ 的运行时间,并获得了(O (1), 6)的二对象近似解,然后我们通过实验证明了我们的算法不仅比以前的工作快得多,而且产生了更低成本的解决方案。
Feb, 2024
本文研究如何在数据中找到低成本的公平聚类问题,针对数据点可能属于多个受保护群体的情况,通过允许用户指定定义公平表示的参数、在任何 Lp 范数目标上工作的聚类算法以及允许个体属于多个保护群体的算法,将任何普通聚类解转换为公平聚类解,实验表明,在实践中算法的表现比理论结果更好。
Jan, 2019
本研究对含 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$-median 和 $k$-means(以及任何使用 $\ell_p$ 范数的 $k$- 聚类),并从个体公平性的角度来考虑。我们的算法提供了一个逼近可行的 $k$- 聚类,其 $k$-median ($k$-means) 的成本与最优的 $k$- 聚类成本相比呈常数比例,并且我们的解决方案大约满足公平条件 (也在常数因子之内)。此外,我们还通过实证评估来补充我们的理论界限。
Feb, 2020