Tight FPT Approximations for k-Median and k-Means
Not on the map. Why?
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.
Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). First posted on arXiv 28 Apr 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 1; 2023: 2; 2024: 2.
7 papers.
- 2022Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Setscited by 14
- 2021Tight FPT Approximation for Socially Fair Clusteringcited by 10
- 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metricscited by 8
- 2023Parameterized Approximation Schemes for Clustering with General Norm Objectivescited by 5
- 2024Diversity-aware clustering: Computational Complexity and Approximation Algorithmscited by 3
- 2023Parameterized Approximation for Robust Clustering in Discrete Geometric Spacescited by 2
- 2024Untangling Gaussian Mixturescited by 0
- 2024Untangling Gaussian Mixtures11 Mar 2024
- 2024Diversity-aware clustering: Computational Complexity and Approximation Algorithms10 Jan 2024
- 2023Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces12 May 2023
- 2023Parameterized Approximation Schemes for Clustering with General Norm Objectives6 Apr 2023
- 2022Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets11 Apr 2022
- 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics21 Nov 2021
- 2021Tight FPT Approximation for Socially Fair Clustering12 Jun 2021