论文标题
公平的五颜六色K-中心群集
Fair Colorful k-Center Clustering
论文作者
论文摘要
彩色k-center实例由彩色红色或蓝色的公制空间中的点以及整数k以及每种颜色的覆盖范围要求组成。目的是找到最小的半径\ r {ho}，以便在满足覆盖范围要求的点的k周围存在半径\ r {ho}的球。这个问题背后的动机是双重的。首先，从公平考虑因素来看：每个颜色/组应获得类似的服务保证，其次，从其提出的算法挑战中：此问题结合了聚类的困难以及子集问题问题。特别是，我们表明，这种组合会导致多种天然线性编程松弛的较强的完整性差距下限。我们的主要结果是一种有效的近似算法，该算法克服了这些困难以获得3个近似保证，几乎与经典k-中心问题的紧密近似保证匹配了2的紧密近似保证，该问题概括了。
An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius \r{ho} such that there exist balls of radius \r{ho} around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes.
