# Parameterized Approximation Algorithms for k-Center Clustering and Variants

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2021.

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

- [Dynamic algorithms for k-center on graphs](https://mlsanity.com/paper/2307.15557/) (2023)

## Abstract (arXiv)

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((klog k)/ε)dn-time (1+ε)-approximation for Euclidean k-center, where d is the dimension. We give a faster algorithm for small dimensions: roughly speaking an O^*(2^O((1/ε)O(d) · k1-1/d · log k))-time (1+ε)-approximation. In particular, the running time is roughly O^*(2^O((1/ε)O(1)√klog 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 2O(klog k)n2 time 3-approximation for NUkC in general metrics, and a 2O((klog k)/ε)dn time (1+ε)-approximation for Euclidean NUkC. The latter time bound matches the bound for k-center.