Approximating Fair $k$-Min-Sum-Radii in Euclidean Space Article Swipe

MAKE IMPACT

Lukas Drexler , Annika Hennes , A. Lahiri , Melanie Schmidt , Julian Wargalla · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2309.00834

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.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2309.00834

PDF

https://arxiv.org/pdf/2309.00834

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4386552427

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4386552427

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2309.00834

Digital Object Identifier

Title

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

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-09-02

Full publication date if available

Authors

Lukas Drexler, Annika Hennes, A. Lahiri, Melanie Schmidt, Julian Wargalla

List of authors in order

Landing page

https://arxiv.org/abs/2309.00834

Publisher landing page

PDF URL

https://arxiv.org/pdf/2309.00834

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2309.00834

Direct OA link when available

Concepts

RADIUS, Combinatorics, Mathematics, Dimension (graph theory), Cluster (spacecraft), Constant (computer programming), Euclidean distance, Base (topology), Euclidean geometry, Domain (mathematical analysis), Cluster analysis, k-means clustering, Discrete mathematics, Mathematical analysis, Geometry, Computer science, Statistics, Computer security, Programming language

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload