# Bicriteria Approximation Algorithms for Priority Matroid Median

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 4 Oct 2022.

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

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Constant-Factor Approximation for Ordered k-Median](https://mlsanity.com/paper/1711.01972/) (2017)
- [A Constant Approximation for Colorful k-Center](https://mlsanity.com/paper/1907.08906/) (2019)
- [Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications](https://mlsanity.com/paper/1310.7834/) (2013)
- [Revisiting Priority k-Center: Fairness and Outliers](https://mlsanity.com/paper/2103.03337/) (2021)

## Abstract (arXiv)

Fairness considerations have motivated new clustering problems and algorithms in recent years. In this paper we consider the Priority Matroid Median problem which generalizes the Priority k-Median problem that has recently been studied. The input consists of a set of facilities F and a set of clients C that lie in a metric space (F cup C,d), and a matroid M=(F,I) over the facilities. In addition each client j has a specified radius rj ≥ 0 and each facility i ∈ F has an opening cost fi. The goal is to choose a subset S subseteq F of facilities to minimize the sumi ∈ F fi + sumj ∈ C d(j,S) subject to two constraints: (i) S is an independent set in M (that is S ∈ I) and (ii) for each client j, its distance to an open facility is at most rj (that is, d(j,S) ≤ rj). For this problem we describe the first bicriteria (c1,c2) approximations for fixed constants c1,c2: the radius constraints of the clients are violated by at most a factor of c1 and the objective cost is at most c2 times the optimum cost. We also improve the previously known bicriteria approximation for the uniform radius setting (rj := L forall j ∈ C).