Exact and approximation algorithms for clustering

In this paper we present a n O(k1�1=d) time algorithm for solving the k-center problem in R d, under L1 and L2 metrics. The algorithm extends to other metrics, and can be used to solve the discrete k-center problem, as well. We also describe a simple (1 +)-approximation algorithm for the k-center problem, with running time O(n log k) + (k = ) O(k1�1=d). Finally, we present a n O(k1�1=d) time algorithm for solving the L-capacitated k-center problem, provided that L = (n=k 1�1=d) or L = O(1). We conclude with a simple approximation algorithm for the L-capacitated k-center problem.