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

Vincent Cohen-Addad, Anupam Gupta, Amit Kumar +2

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 approximat…