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
