Parameterized Approximation Algorithms for $k$-Center Clustering and Variants

Abstract

$k$-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.93, even in the plane, if one insists the dependence on $k$ in the running time be polynomial. Without this restriction, a classic algorithm yields a $2^{O((k\log k)/\epsilon )}dn$-time $(1+\epsilon )$-approximation for Euclidean $k$-center, where $d$ is the dimension. We give a faster algorithm for small dimensions: roughly speaking an $O^{\ast }(2^{O((1/\epsilon {)}^{O(d)}\cdot k^{1-1/d}\cdot \log k)})$-time $(1+\epsilon )$-approximation. In particular, the running time is roughly $O^{\ast }(2^{O((1/\epsilon {)}^{O(1)}\sqrt{k}\log k)})$ in the plane. We complement our algorithmic result with a matching hardness lower bound. We also consider a well-studied generalization of $k$-center, called Non-uniform $k$-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a $2^{O(k\log k)}{n}^2$ time $3$-approximation for NUkC in general metrics, and a $2^{O((k\log k)/\epsilon )}dn$ time $(1+\epsilon )$-approximation for Euclidean NUkC. The latter time bound matches the bound for $k$-center.

A preliminary version appears in AAAI 2022