posted on 2024-07-25, 12:39authored byFateme Abbasi, Sandip Banerjee, Jaros law Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel MarxDániel Marx, Roohani Sharma, Joachim Spoerhase
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 → ℝ_{≥ 0} and a positive integer k. Further, each point belongs to one (or more) of the m many different groups S_1,S_2,…,S_m ⊆ P. Our goal is to find a set X of k centers such that max_{i ∈ [m]} ∑_{p ∈ S_i} 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)] 1) For a universal constant η₀ > 0.0006, we devise a 3^z(1-η₀)-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 3^z for general metrics [Goyal, Jaiswal, Inf. Proc. Letters, 2023] no longer holds when the metric has geometric structure. 2) We show that Robust (k,z)-Clustering in discrete Euclidean spaces is (√{3/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]. 3) 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.
History
Editor
Bringmann K ; Grohe M ; Puppis G ; Svensson O
Primary Research Area
Algorithmic Foundations and Cryptography
Name of Conference
International Colloquium on Automata Languages and Programming (ICALP)
Journal
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Volume
297
Page Range
6:1-6:19
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
BibTeX
@inproceedings{Abbasi:Banerjee:Byrka:Chalermsook:Gadekar:Khodamoradi:Marx:Sharma:Spoerhase:2024,
title = "Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces",
author = "Abbasi, Fateme" AND "Banerjee, Sandip" AND "Byrka, Jaros law" AND "Chalermsook, Parinya" AND "Gadekar, Ameet" AND "Khodamoradi, Kamyar" AND "Marx, Dániel" AND "Sharma, Roohani" AND "Spoerhase, Joachim",
editor = "Bringmann, Karl" AND "Grohe, Martin" AND "Puppis, Gabriele" AND "Svensson, Ola",
year = 2024,
month = 7,
journal = "51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)",
pages = "6:1--6:19",
publisher = "Schloss Dagstuhl – Leibniz-Zentrum für Informatik",
issn = "1868-8969",
doi = "10.4230/LIPIcs.ICALP.2024.6"
}