mlsanityData to 14 Oct 2026

Bicriteria Approximation Algorithms for Priority Matroid Median

arXiv 2210.01888 ↗First posted 4 Oct 2022cs.DS cs.LGcited by 0

Not on the map. Why?

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).

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

13 of 37 references.

References · 13

  1. 2018Fair Clustering Through Fairletscited by 176
  2. 2019Fair k-Center Clustering for Data Summarizationcited by 65
  3. 2020Individual Fairness for k-Clusteringcited by 56
  4. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  5. 2020Fair clustering via equitable group representationscited by 43
  6. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  7. 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
  8. 2019A Center in Your Neighborhood: Fairness in Facility Locationcited by 26
  9. 2017Constant Approximation for k-Median and k-Means with Outliers via Iterative Roundingcited by 25
  10. 2017Constant-Factor Approximation for Ordered k-Mediancited by 8
  11. 2019A Constant Approximation for Colorful k-Centercited by 7
  12. 2013Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applicationscited by 4
1 more
  1. 2021Revisiting Priority k-Center: Fairness and Outlierscited by 4

Built on by

Not cited yet.