In this paper we present an n(O(k1 − 1/d))-time algorithm for solving the k-center problem in R − d, under L∞ and L2 metrics. The algorithm extends to other metrics, and to the discrete k-center problem. 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 an 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).
