2026-07-30T22:42:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14090 2024-03-06T10:53:26Z ddc:004 open_access

Revisiting Priority k-Center: Fairness and Outliers Bajpai, Tanvi Chakrabarty, Deeparnab Chekuri, Chandra Negahbani, Maryam Fairness Clustering Approximation Outliers 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 max_{v ∈ X} 1/(r(v)) d(v,S). If all r(v)’s were uniform, one obtains the classical k-center problem. Plesník [Ján Plesník, 1987] introduced this problem and gave a 2-approximation algorithm matching the best possible algorithm for vanilla k-center. We show how the Priority k-Center problem is related to two different notions of fair clustering [Harris et al., 2019; Christopher Jung et al., 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tanvi Bajpai and Deeparnab Chakrabarty and Chandra Chekuri and Maryam Negahbani 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.21 urn:nbn:de:0030-drops-140909 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.21 eng https://creativecommons.org/licenses/by/4.0/legalcode