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. 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 S_1,S_2,,S_m. Our goal is to find a set X of k centers such that _i [m] _p S_i 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( m/ 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 (3^z+)-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 3^z(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 ( 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.

Tasks

Reproductions