In this paper we present an nˆ O(k
1‐1/d
) ‐time algorithm for solving the k ‐center problem in eals
d
, under L
∈
fty ‐ and L
2
‐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(nlog k) + (k/ϵ)ˆ O(k
1‐1/d
) . Finally, we present an nˆ O(k
1‐1/d
) ‐time algorithm for solving the L ‐capacitated k ‐center problem, provided that L=Ω(n/k
1‐1/d
) or L=O(1) .
