2021/03/04 by Bajpai, Tanvi, Chakrabarty, Deeparnab, Chekuri, Chandra +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2103.03337
In the Priority k-Center problem, the input consists of a metric space (X,d), an integer k, and for each point v ∈ X a priority radius r(v). The goal is to choose k-centers S ⊆ X to minimize maxv ∈ X (1)/(r(v)) d(v,S). If all r(v)'s are uniform, one obtains the k-Center problem. Plesník [Plesník, Disc. Appl. Math. 1987] introduced the Priority k-Center problem and gave a 2-approximation algorithm matching the best possible algorithm for k-Center. We show how the problem is related to two different notions of fair clustering [Harris et al., NeurIPS 2018; Jung et al., FORC 2020]. Motivated by these developments we revisit the problem and, in our main technical contribution, develop a framework that yields constant factor approximation algorithms for Priority k-Center with outliers. Our framework extends to generalizations of Priority k-Center to matroid and knapsack constraints, and as a corollary, also yields algorithms with fairness guarantees in the lottery model of Harris et al [Harris et al, JMLR 2019].