文章基本信息

标题：Service in Your Neighborhood: Fairness in Center Location
本地全文：下载
作者：Christopher Jung ; Sampath Kannan ; Neil Lutz 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：156
页码：5:1-5:15
DOI：10.4230/LIPIcs.FORC.2020.5
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Fairness; Clustering; Facility Location