Euclidean k-center Fair Clusterings
Ayano Moritaka, Shin-ichi Nakano, Kento Tanaka, Noriaki Yoshida
许多近似算法和找公平聚类的思潮算法已经出现。 在本文中,我们定义了公平聚类问题的新自然变体,并设计了一个多项式时间算法来计算最优的公平聚类。 让P是平面上的一组n点,并且每个点在C中有一个颜色,对应于一个组。 对于 C 中的每个颜色 q,给出一个下限 l(q) 和一个上界 u(q)。 然后我们定义公平聚类问题如下。 公平的 k 集群问题是将 P 的分区找到一组 k 群集,成本最低,因此每个群集至少包含 l(q) 和 P 中的最多 u(q) 点。 通过 l(q) 和 u(q),每个群集不能包含太少或太多具有特定颜色的点。 如果我们认为一种颜色属于性别或少数民族群体,则聚类对应于公平的聚类。
Many approximation algorithms and heuristic algorithms to find a fair clustering have emerged. In this paper we define a new and natural variant of fair clustering problem and design a polynomial time algorithm to compute an optimal fair clustering. Let P be a set of n points on a plane, and each point has a color in C, corresponding to a group. For each color q in C, a lower bound l(q) and an upper bound u(q) are given. Then we define the fair clustering problem as follows. The fair k-clusterin...