Metraipolis › archive › dc_f1ce16cb42ee

Socially Fair Clustering: Parameterized Approximation and Local Search — arXiv:2608.30026

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.30026
License (as archived)
CC0-1.0
Archived
2026-10-17T10:07:10.040Z
SHA-256 of the archived text
8a85aea88f866b2ae82f5bd38987e9aea14bc74b3936dd4ad4b09911666235c8
Stable URL of this page
https://metraipolis.com/documento/dc_f1ce16cb42ee

How to cite

Socially Fair Clustering: Parameterized Approximation and Local Search — arXiv:2608.30026 — arXiv (en), https://arxiv.org/abs/2608.30026 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f1ce16cb42ee (Metraipolis archive dc_f1ce16cb42ee, sha256 8a85aea88f866b2ae82f5bd38987e9aea14bc74b3936dd4ad4b09911666235c8)
BibTeX
@misc{dcf1ce16cb42ee,
  title = {Socially Fair Clustering: Parameterized Approximation and Local Search — arXiv:2608.30026},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.30026},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f1ce16cb42ee; sha256 8a85aea88f866b2ae82f5bd38987e9aea14bc74b3936dd4ad4b09911666235c8},
  year = {2026}
}

Archived text

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

We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021), along with its extension, the $(p,q)$-Socially Fair Clustering problem. This problem generalizes $k$-medians and $k$-means to settings where data points are partitioned into $\ell$ groups, and the goal is to find a fair clustering that is simultaneously good for all groups. We present several algorithms for this problem. For $\ell_p$-Socially Fair Clustering, we give the first constant-factor FPT-approximation parameterized by the number of groups $\ell$, resolving the open question raised by Ghadiri, Singh, and Vempala (2022). Our main ingredient is a new algorithm for closing additional centers in parameterized time inspired by local search. We then turn to the more general $(p,q)$-Socially Fair Clustering problem. The known algorithm for this problem, proposed by Chlamtáč, Makarychev, and Vakilian (2022) achieves a very good approximation but is complex, slow and difficult to implement. We analyze the performance of a simple local search algorithm and show that it provides an $O(q)$ approximation in the worst case. Finally, we design approximation algorithms for the facility location variant of the problem, where the number of facilities (centers) is not fixed in advance, and opening each facility incurs an opening cost. Unlike in previous work, we do not assume these opening costs are the same for all groups.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.30026 — 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-17T10:00:01.287Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).