Parameterized Approximation Algorithms for K-center Clustering and Variants

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

Authors

• Sayan Bandyapadhyay
• Zachary Friggstad
• Ramin Mousavi

Keywords

No keywords are indexed for this paper.