Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces

We consider the well-studied Robust (k, z)-Clustering problem, which generalizes the classic k-Median, k-Means, and k-Center problems. Given a constant z≥ 1, the input to Robust (k, z)-Clustering is a set P of n weighted points in a metric space (M,δ) and a positive integer k. Further, each point belongs to one (or more) of the m many different groups S1,S2,ldots,Sm. Our goal is to find a set X of k centers such that maxi ∈ [m] sump ∈ Si w(p) δ(p,X)z is minimized. This problem arises in the domains of robust optimization [Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness. For polynomial time computation, an approximation factor of O(log m/loglog m) is known [Makarychev, Vakilian, COLT 2021], which is tight under a plausible complexity assumption even in the line metrics. For FPT time, there is a (3z+ε)-approximation algorithm, which is tight under GAP-ETH [Goyal, Jaiswal, Inf. Proc. Letters, 2023]. Motivated by the tight lower bounds for general discrete metrics, we focus on geometric spaces such as the (discrete) high-dimensional Euclidean setting and metrics of low doubling dimension, which play an important role in data analysis applications. First, for a universal constant η0 >0.0006, we devise a 3z(1-η0)-factor FPT approximation algorithm for discrete high-dimensional Euclidean spaces thereby bypassing the lower bound for general metrics. We complement this result by showing that even the special case of k-Center in dimension Theta(log n) is (√3/2- o(1))-hard to approximate for FPT algorithms. Finally, we complete the FPT approximation landscape by designing an FPT (1+ε)-approximation scheme (EPAS) for the metric of sub-logarithmic doubling dimension.