Fair k-Centers via Maximum Matching
Fair k-Centers via Maximum Matching
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Matthew D. Jones;Huy L. Nguyen;Thy Nguyen
中科院分区：
文献类型：
--
作者：
Matthew D. Jones;Huy L. Nguyen;Thy Nguyen
在最近的历史中，算法领域已经看到了对公平性的推动，或者消除固有偏见。在数据汇总中，选择数据集的一个小得多的子集来代表整个数据，可以通过保证每个“人口统计组”代表子集的特定部分来引入公平性。具体来说，本文研究了k -中心问题的这种公平变体，其中选择基数为k的数据子集以最小化与其余数据的距离。以往的研究工作都提出了一个3-近似算法与超线性运行时间和线性时间算法，其近似因子是指数的人口统计组的数量。本文结合了最好的每个算法，提出了一个线性时间算法，保证3-近似因子，并提供了经验证据的算法的运行时间和有效性。
The field of algorithms has seen a push for fairness, or the removal of inherent bias, in recent history. In data summarization, where a much smaller subset of a data set is chosen to represent the whole of the data, fairness can be introduced by guaranteeing each "demographic group" a spe-cific portion of the representative subset. Specifi-cally, this paper examines this fair variant of the k -centers problem, where a subset of the data with cardinality k is chosen to minimize distance to the rest of the data. Previous papers working on this problem presented both a 3-approximation algo-rithm with a super-linear runtime and a linear-time algorithm whose approximation factor is exponential in the number of demographic groups. This paper combines the best of each algorithm by presenting a linear-time algorithm with a guaranteed 3-approximation factor and provides empirical evidence of both the algorithm’s runtime and effectiveness.