论文标题
公平范围K-Center
Fair Range k-center
论文作者
论文摘要
我们研究了K-Centers在具有不相交人群组的数据上的公平性问题。具体而言，这项工作提出了一种公平性的变体，该变量限制了每个组的下限（少数群体保护）和上限（限制性义务）的中心数，并为问题提供了一个离线和一通流算法。在下限和上限相同的特殊情况下，我们的离线算法保留了与先前的最新时间的相同时间复杂性和近似因素。此外，与以前的工作相比，我们的一通流算法在此特殊情况下的近似因素，运行时间和空间复杂性提高了。具体而言，与先前的17个附属算法相比，我们的算法的近似因子为13，并且先前算法的时间复杂性取决于公制纵横远景比，这可以任意较大，而我们的算法的运行时间不依赖于纵横比的运行时间。
We study the problem of fairness in k-centers clustering on data with disjoint demographic groups. Specifically, this work proposes a variant of fairness which restricts each group's number of centers with both a lower bound (minority-protection) and an upper bound (restricted-domination), and provides both an offline and one-pass streaming algorithm for the problem. In the special case where the lower bound and the upper bound is the same, our offline algorithm preserves the same time complexity and approximation factor with the previous state-of-the-art. Furthermore, our one-pass streaming algorithm improves on approximation factor, running time and space complexity in this special case compared to previous works. Specifically, the approximation factor of our algorithm is 13 compared to the previous 17-approximation algorithm, and the previous algorithms' time complexities have dependence on the metric space's aspect ratio, which can be arbitrarily large, whereas our algorithm's running time does not depend on the aspect ratio.
