论文标题
公平的相关聚类
Fair Correlation Clustering
论文作者
论文摘要
在本文中，我们研究了在公平限制下的相关聚类。最近已经研究了$ k $ -Median和$ k $ center聚类的公平变体，并且已经提出了使用称为Fairlet分解的概念的近似算法。在几种重要类型的公平约束下，我们获得了公平相关聚类的近似算法。 我们的结果取决于通过引入一种新型组合优化问题来获得相关聚类的FAILLET分解。我们定义了一个类似于$ k $ -Median成本的成本的Fairlet分解，这使我们能够获得有关广泛公平限制的近似算法。 我们通过对真实图上的算法进行深入分析，对我们的理论结果进行补充，在该分析中，与最先进的（不公平）算法相比，成本增加的相关性聚类解决方案可以获得公平的相关聚类解决方案。
In this paper, we study correlation clustering under fairness constraints. Fair variants of $k$-median and $k$-center clustering have been studied recently, and approximation algorithms using a notion called fairlet decomposition have been proposed. We obtain approximation algorithms for fair correlation clustering under several important types of fairness constraints. Our results hinge on obtaining a fairlet decomposition for correlation clustering by introducing a novel combinatorial optimization problem. We define a fairlet decomposition with cost similar to the $k$-median cost and this allows us to obtain approximation algorithms for a wide range of fairness constraints. We complement our theoretical results with an in-depth analysis of our algorithms on real graphs where we show that fair solutions to correlation clustering can be obtained with limited increase in cost compared to the state-of-the-art (unfair) algorithms.
