Colorful Priority k-Supplier

In the Priority k-Supplier problem the input consists of a metric space (F ∪ C, d) over set of facilities F and a set of clients C, an integer $k > 0$, and a non-negative radius rᵥ for each client v ∈ C. The goal is to select k facilities S ⊆ F to minimize maxv ∈ C d(v,S)/rᵥ where $d(v,S)$ is the distance of v to the closes facility in S. This problem generalizes the well-studied k-Center and k-Supplier problems, and admits a $3$-approximation [Plesn\'ik, 1987, Bajpai et al., 2022. In this paper we consider two outlier versions. The Priority k-Supplier with Outliers problem [Bajpai et al., 2022] allows a specified number of outliers to be uncovered, and the Priority Colorful k-Supplier problem is a further generalization where clients are partitioned into c colors and each color class allows a specified number of outliers. These problems are partly motivated by recent interest in fairness in clustering and other optimization problems involving algorithmic decision making. We build upon the work of [Bajpai et al., 2022] and improve their $9$-approximation Priority k-Supplier with Outliers problem to a 1+3√3≈ 6.196-approximation. For the Priority Colorful k-Supplier problem, we present the first set of approximation algorithms. For the general case with c colors, we achieve a $17$-pseudo-approximation using $k+2c-1$ centers. For the setting of $c=2$, we obtain a $7$-approximation in random polynomial time, and a 2+√5≈ 4.236-pseudo-approximation using $k+1$ centers.