Approximating Fair $k$-Min-Sum-Radii in $\mathbb{R}^d$
Lukas Drexler Annika Hennes Abhiruk Lahiri Melanie Schmidt Julian Wargalla
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 $\mathbb{R}^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.