Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
share
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 max_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(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 (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 Θ(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.
READ FULL TEXT