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

Amit Kumar; Anupam Gupta; Euiwoong Lee; Jason Li; Vincent Cohen-Addad

arxiv: 1904.12334 · v1 · pith:TKFLNHHRnew · submitted 2019-04-28 · 💻 cs.DS

Tight FPT Approximations for k-Median and k-Means

Vincent Cohen-Addad , Anupam Gupta , Amit Kumar , Euiwoong Lee , Jason Li This is my paper

classification 💻 cs.DS

keywords meansmediantimevarepsilonalgorithmsapproximatingapproximationapproximations

0 comments

read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Approximation Preserving Coresets
cs.DS 2026-06 unverdicted novelty 6.0

Introduces approximation-preserving coresets that guarantee cost preservation for near-optimal solutions and proves that even tiny approximation-factor distortion forbids coresets of that size.