Service in Your Neighborhood: Fairness in Center Location
Service in Your Neighborhood: Fairness in Center Location
复制标题
DOI：
10.4230/lipics.forc.2020.5
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Christopher Jung;Sampath Kannan;Neil Lutz
中科院分区：
文献类型：
--
作者：
Christopher Jung;Sampath Kannan;Neil Lutz
在选择一组中心的位置时，标准的聚类算法可能会在某些人和社区上燃烧，尤其是将当地人口密度考虑在内。我们将单个I的“邻域半径”定义为以I至少N/K个体的I的最小半径。在她的邻居半径中，我们提出了几个理论结果：我们表明，优化该因素是NP，我们提供了一种近似算法，可确保最多2个公制空间。 。
When selecting locations for a set of centers, standard clustering algorithms may place unfair burden on some individuals and neighborhoods. We formulate a fairness concept that takes local population densities into account. In particular, given k centers to locate and a population of size n , we define the “neighborhood radius” of an individual i as the minimum radius of a ball centered at i that contains at least n/k individuals. Our objective is to ensure that each individual has a center that is within at most a small constant factor of her neighborhood radius . We present several theoretical results: We show that optimizing this factor is NP-hard; we give an approximation algorithm that guarantees a factor of at most 2 in all metric spaces; and we prove matching lower bounds in some metric spaces. We apply a variant of this algorithm to real-world address data, showing that it is quite different from standard clustering algorithms and outperforms them on our objective function and balances the load between centers more evenly.