# Tight FPT Approximations for k-Median and k-Means

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2019.

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

- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces](https://mlsanity.com/paper/2305.07316/) (2023)
- [Untangling Gaussian Mixtures](https://mlsanity.com/paper/2403.06671/) (2024)

## Abstract (arXiv)

We investigate the fine-grained complexity of approximating the classical k-median / k-means clustering problems in general metric spaces. We show how to improve the approximation factors to (1+2/e+varepsilon) and (1+8/e+varepsilon) respectively, using algorithms that run in fixed-parameter time. Moreover, we show that we cannot do better in FPT time, modulo recent complexity-theoretic conjectures.