# Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces

arXiv: https://arxiv.org/abs/2305.07316 · HTML: https://mlsanity.com/paper/2305.07316/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 12 May 2023.

## Builds on (most cited first, 16 of 16)

- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [On Approximability of Clustering Problems Without Candidate Centers](https://mlsanity.com/paper/2010.00087/) (2020)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Coresets for Clustering in Graphs of Bounded Treewidth](https://mlsanity.com/paper/1907.04733/) (2019)
- [Coresets for Ordered Weighted Clustering](https://mlsanity.com/paper/1903.04351/) (2019)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Tight FPT Approximations for k-Median and k-Means](https://mlsanity.com/paper/1904.12334/) (2019)
- [A Refined Approximation for Euclidean k-Means](https://mlsanity.com/paper/2107.07358/) (2021)
- [New Approximability Results for the Robust k-Median Problem](https://mlsanity.com/paper/1309.4602/) (2013)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)

## Built on by (most cited first, 2 of 2)

- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights](https://mlsanity.com/paper/2410.12913/) (2024)

## Abstract (arXiv)

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.