Fair colorful k-center clustering
研究了多彩k-中心问题，即度量空间中红蓝两色点需满足各自覆盖要求，提出近似比为3的算法，接近经典k-中心问题的紧界2。
Abstract 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 $$\rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ρ</mml:mi> </mml:math> such that there exist balls of radius $$\rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ρ</mml:mi> </mml:math> 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. algorithms either opened more than k centers or only worked in the special case when the input points are in the plane.