# New Approximation Algorithms for Fair k-median Problem

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2022.

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

- [Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems](https://mlsanity.com/paper/2411.01115/) (2024)

## Abstract (arXiv)

The fair k-median problem is one of the important clustering problems. The current best approximation ratio is 4.675 for this problem with 1-fair violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. As far as we know, there is no available approximation algorithm for the problem without any fair violation. In this paper, we consider the fair k-median problem in bounded doubling metrics and general metrics. We provide the first QPTAS for fair k-median problem in doubling metrics. Based on the split-tree decomposition of doubling metrics, we present a dynamic programming process to find the candidate centers, and apply min-cost max-flow method to deal with the assignment of clients. Especially, for overcoming the difficulties caused by the fair constraints, we construct an auxiliary graph and use minimum weighted perfect matching to get part of the cost. For the fair k-median problem in general metrics, we present an approximation algorithm with ratio O(log k), which is based on the embedding of given space into tree metrics, and the dynamic programming method. Our two approximation algorithms for the fair k-median problem are the first results for the corresponding problems without any fair violation, respectively.