Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces

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.