2026-09-10T09:44:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27720 2026-09-09T12:19:35Z ddc:004 open_access

Socially Fair Clustering: Parameterized Approximation and Local Search Anand, Aditya Makarychev, Yury Shan, Liren Socially fair clustering Approximation algorithms Fixed-parameter tractability Local search Facility location k-median and k-means We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian [Abbasi et al., 2021] and by Ghadiri, Samadi, and Vempala [Ghadiri et al., 2021], along with its extension, the (p,q)-Socially Fair Clustering problem. This problem generalizes k-median and k-means to settings where data points are partitioned into 𝓁 groups, and the goal is to find a fair clustering that is simultaneously good for all groups. We present several algorithms for this problem. 1) For 𝓁_p-Socially Fair Clustering, we give the first constant-factor FPT-approximation parameterized by the number of groups 𝓁, resolving the open question raised by Ghadiri, Singh, and Vempala [Ghadiri et al., 2022]. Our main ingredient is a new algorithm for closing additional centers in parameterized time inspired by local search. 2) 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 [Chlamtáč et al., 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. 3) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aditya Anand and Yury Makarychev and Liren Shan 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.3 urn:nbn:de:0030-drops-277207 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode