# Approximating Fair k-Min-Sum-Radii in Euclidean Space

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 2 Sep 2023.

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

- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [KFC: A Scalable Approximation Algorithm for k-center Fair Clustering](https://mlsanity.com/paper/2010.13949/) (2020)
- [Fair Clustering with Multiple Colors](https://mlsanity.com/paper/2002.07892/) (2020)
- [Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers](https://mlsanity.com/paper/1608.01700/) (2016)
- [Dynamic clustering to minimize the sum of radii](https://mlsanity.com/paper/1707.02577/) (2017)
- [Achieving anonymity via weak lower bound constraints for k-median and k-means](https://mlsanity.com/paper/2009.03078/) (2020)
- [FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii](https://mlsanity.com/paper/2303.07923/) (2023)

## Abstract (arXiv)

The k-center problem is a classical clustering problem in which one is asked to find a partitioning of a point set P into k clusters such that the maximum radius of any cluster is minimized. It is well-studied. But what if we add up the radii of the clusters instead of only considering the cluster with maximum radius? This natural variant is called the k-min-sum-radii problem. It has become the subject of more and more interest in recent years, inspiring the development of approximation algorithms for the k-min-sum-radii problem in its plain version as well as in constrained settings. We study the problem for Euclidean spaces ℝd of arbitrary dimension but assume the number k of clusters to be constant. In this case, a PTAS for the problem is known (see Bandyapadhyay, Lochet and Saurabh, SoCG, 2023). Our aim is to extend the knowledge base for k-min-sum-radii to the domain of fair clustering. We study several group fairness constraints, such as the one introduced by Chierichetti et al. (NeurIPS, 2017). In this model, input points have an additional attribute (e.g., colors such as red and blue), and clusters have to preserve the ratio between different attribute values (e.g., have the same fraction of red and blue points as the ground set). Different variants of this general idea have been studied in the literature. To the best of our knowledge, no approximative results for the fair k-min-sum-radii problem are known, despite the immense amount of work on the related fair k-center problem. We propose a PTAS for the fair k-min-sum-radii problem in Euclidean spaces of arbitrary dimension for the case of constant k. To the best of our knowledge, this is the first PTAS for the problem. It works for different notions of group fairness.