# Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces

Loading...

##### Access rights

openAccess

##### Journal Title

##### Journal ISSN

##### Volume Title

Conference article in proceedings

This publication is imported from Aalto University research portal.

View publication in the Research portal

View/Open full text file from the Research portal

Other link related to publication

View publication in the Research portal

View/Open full text file from the Research portal

Other link related to publication

##### Date

2024-07

##### Department

##### Major/Subject

##### Mcode

##### Degree programme

##### Language

en

##### Pages

##### Series

Leibniz International Proceedings in Informatics, LIPIcs ; Volume 297

##### Abstract

We consider the well-studied Robust (k, z)-Clustering problem, which generalizes the classic k-Median, k-Means, and k-Center problems and arises in the domains of robust optimization [Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness [Abbasi, Bhaskara, Venkatasubramanian, 2021 & Ghadiri, Samadi, Vempala, 2022]. Given a constant z ≥ 1, the input to Robust (k, z)-Clustering is a set P of n points in a metric space (M, δ), a weight function w : P → R≥0 and a positive integer k. Further, each point belongs to one (or more) of the m many different groups S1, S2, . . ., Sm ⊆ P. Our goal is to find a set X of k centers such that maxi∈[m]Pp∈Si w(p)δ(p, X)z is minimized. Complementing recent work on this problem, we give a comprehensive understanding of the parameterized approximability of the problem in geometric spaces where the parameter is the number k of centers. We prove the following results: (i) For a universal constant η0 > 0.0006, we devise a 3z(1−η0)-factor FPT approximation algorithm for Robust (k, z)-Clustering in discrete high-dimensional Euclidean spaces where the set of potential centers is finite. This shows that the lower bound of 3z for general metrics [Goyal, Jaiswal, Inf. Proc. Letters, 2023] no longer holds when the metric has geometric structure. (ii) We show that Robust (k, z)-Clustering in discrete Euclidean spaces is (p3/2−o(1))-hard to approximate for FPT algorithms, even if we consider the special case k-Center in logarithmic dimensions. This rules out a (1 + ϵ)-approximation algorithm running in time f(k, ϵ)poly(m, n) (also called efficient parameterized approximation scheme or EPAS), giving a striking contrast with the recent EPAS for the continuous setting where centers can be placed anywhere in the space [Abbasi et al., FOCS’23]. (iii) However, we obtain an EPAS for Robust (k, z)-Clustering in discrete Euclidean spaces when the dimension is sublogarithmic (for the discrete problem, earlier work [Abbasi et al., FOCS’23] provides an EPAS only in dimension o(log log n)). Our EPAS works also for metrics of sub-logarithmic doubling dimension.##### Description

Publisher Copyright: © Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase.

##### Keywords

approximation algorithms, Clustering, parameterized complexity

##### Other note

##### Citation

Abbasi, F, Byrka, J, Gadekar, A, Marx, D, Spoerhase, J, Banerjee, S, Chalermsook, P, Khodamoradi, K & Sharma, R 2024, Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces . in K Bringmann, M Grohe, G Puppis & O Svensson (eds), 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024 ., 6, Leibniz International Proceedings in Informatics, LIPIcs, vol. 297, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Colloquium on Automata, Languages, and Programming, Tallinn, Estonia, 08/07/2024 . https://doi.org/10.4230/LIPIcs.ICALP.2024.6