Metraipolis › archive › dc_723e3055f92f
Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering — arXiv:2609.06384
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.06384
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:56:46.075Z
- SHA-256 of the archived text
9eb4a96be819598ae7c0a12bc0193761ce01cacd71bf1d679c259a31d7764df3- Stable URL of this page
https://metraipolis.com/documento/dc_723e3055f92f
How to cite
Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering — arXiv:2609.06384 — arXiv (en), https://arxiv.org/abs/2609.06384 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_723e3055f92f (Metraipolis archive dc_723e3055f92f, sha256 9eb4a96be819598ae7c0a12bc0193761ce01cacd71bf1d679c259a31d7764df3)
BibTeX
@misc{dc723e3055f92f,
title = {Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering — arXiv:2609.06384},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.06384},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_723e3055f92f; sha256 9eb4a96be819598ae7c0a12bc0193761ce01cacd71bf1d679c259a31d7764df3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06384. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LG). Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI). Pagina del lavoro: https://arxiv.org/abs/2609.06384 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T13:39:42.863Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).