# Revisiting Priority k-Center: Fairness and Outliers

arXiv: https://arxiv.org/abs/2103.03337 · HTML: https://mlsanity.com/paper/2103.03337/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 4 Mar 2021.

## Builds on (most cited first, 14 of 14)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Matroid and Knapsack Center Problems](https://mlsanity.com/paper/1301.0745/) (2013)
- [A Technique for Obtaining True Approximations for k-Center with Covering Constraints](https://mlsanity.com/paper/2007.03946/) (2020)
- [Fair Colorful k-Center Clustering](https://mlsanity.com/paper/2007.04059/) (2020)
- [The Non-Uniform k-Center Problem](https://mlsanity.com/paper/1605.03692/) (2016)
- [A Lottery Model for Center-type Problems With Outliers](https://mlsanity.com/paper/1710.00287/) (2017)
- [Approximation algorithms for stochastic clustering](https://mlsanity.com/paper/1809.02271/) (2018)
- [A Constant Approximation for Colorful k-Center](https://mlsanity.com/paper/1907.08906/) (2019)
- [Generalized Center Problems with Outliers](https://mlsanity.com/paper/1805.02217/) (2018)
- [Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations](https://mlsanity.com/paper/1806.04202/) (2018)

## Built on by (most cited first, 4 of 4)

- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Bicriteria Approximation Algorithms for Priority Matroid Median](https://mlsanity.com/paper/2210.01888/) (2022)

## Abstract (arXiv)

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 subseteq X to minimize maxv ∈ X frac1r(v) d(v,S). If all r(v)'s are uniform, one obtains the k-Center problem. Plesn'ik [Plesn'ik, 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].