# Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 6 Sep 2026.

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

- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [How to Solve Fair k-Center in Massive Data Models](https://mlsanity.com/paper/2002.07682/) (2020)
- [Tight FPT Approximation for Constrained k-Center and k-Supplier](https://mlsanity.com/paper/2110.14242/) (2021)
- [Core-sets for Fair and Diverse Data Summarization](https://mlsanity.com/paper/2310.08122/) (2023)
- [Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge](https://mlsanity.com/paper/2401.12533/) (2024)
- [Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights](https://mlsanity.com/paper/2410.12913/) (2024)
- [Improved Streaming Algorithm for Fair k-Center Clustering](https://mlsanity.com/paper/2510.05937/) (2025)
- [Optimized Algorithms for Text Clustering with LLM-Generated Constraints](https://mlsanity.com/paper/2601.11118/) (2026)
- [Approximation Algorithm for Constrained k-Center Clustering: A Local Search Approach](https://mlsanity.com/paper/2601.11883/) (2026)

## Abstract (arXiv)

Motivated by the growing importance of fairness in machine learning, fair k-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into m disjoint groups, and the objective is to select k data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair k-center with an approximation ratio of 2.732. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of 4.464. These ratios can be further respectively improved to 2.414 and 3.828 with a runtime exponential on k. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of 4.732, which can be further improved to 4.42, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.