Fast Approximate ℓ-Center Clustering in High-Dimensional Spaces

We study the design of efficient approximation algorithms for the ℓ-center clustering and minimum-diameter ℓ-clustering problems in high-dimensional Euclidean and Hamming spaces. Our main tool is randomized dimension reduction. First, we present a general method of reducing the dependency of the running time of a hypothetical algorithm for the ℓ-center problem in a high-dimensional Euclidean space on the dimension. Utilizing this method in part, we provide (2+ϵ)-approximation algorithms for the ℓ-center clustering and minimum-diameter ℓ-clustering problems in Euclidean and Hamming spaces that are substantially faster than the known 2-approximation algorithms when both ℓ and the dimension are super-logarithmic. Next, we apply the general method to the recent fast approximation algorithms with higher approximation guarantees for the ℓ-center clustering problem in a high-dimensional Euclidean space. Finally, we provide a speed-up of the known O(1)-approximation method for the generalization of the ℓ-center clustering problem that allows z outliers (i.e., z input points may be ignored when computing the maximum distance from an input point to a center) in high-dimensional Euclidean and Hamming spaces.