Metraipolis › archive › dc_45bceea7bb07

Subexponential Parameterized Approximation for Group-Fair Euclidean $k$-Center — arXiv:2610.20250

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.20250
License (as archived): CC0-1.0
Archived: 2026-10-15T21:58:28.346Z
SHA-256 of the archived text: d088701f359635cebb26b1723f3eed7d67749cf1a994790425d13b38018a743c
Stable URL of this page: https://metraipolis.com/documento/dc_45bceea7bb07

How to cite

Subexponential Parameterized Approximation for Group-Fair Euclidean $k$-Center — arXiv:2610.20250 — arXiv (en), https://arxiv.org/abs/2610.20250 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_45bceea7bb07 (Metraipolis archive dc_45bceea7bb07, sha256 d088701f359635cebb26b1723f3eed7d67749cf1a994790425d13b38018a743c)

BibTeX

@misc{dc45bceea7bb07,
  title = {Subexponential Parameterized Approximation for Group-Fair Euclidean $k$-Center — arXiv:2610.20250},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.20250},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_45bceea7bb07; sha256 d088701f359635cebb26b1723f3eed7d67749cf1a994790425d13b38018a743c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20250. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Clustering is a basic tool for grouping data into meaningful classes, but in many applications the resulting clusters must also respect the fairness conditions among different groups. We study this direction for the group-fair Euclidean $k$-center problem in fixed dimension, where the input points are partitioned into disjoint color classes, and every cluster must satisfy given lower and upper bounds on the fraction of each color. We give a separator-based recursive approximation algorithm for the continuous-center setting. The main idea is to first reduce the continuous search space to a finite candidate center set and then use the geometric sphere separators to break the instance into smaller subproblems. Our algorithm gives a bicriteria approximation: the clustering radius is within a factor of $(1+\epsilon)$ of the optimum exactly fair solution, while the fairness bounds are relaxed only by a multiplicative factor. For fixed dimension, number of colors, and approximation parameters, the running time is polynomial in input size and subexponential in $k$. A recent IJCAI-ECAI2026 result gives a $(1+\epsilon)$-approximation for group-fair $k$-center in bounded doubling metrics with running time $(k/\epsilon)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. In the fixed-dimensional Euclidean setting considered here, we improve the dependence on $k$ to subexponential, while allowing continuous centers. The fairness guarantees of the two results are different: the previous work allows an additive fairness violation, whereas our algorithm uses a controlled multiplicative relaxation.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.20250 — 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-15T21:39:44.504Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).