On approximate geometric k-clustering

For a partition of an n-point set X subset of R-d into k subsets (clusters) S-1, S-2, ..., S-k, we consider the cost function Sigma(i=1)(k) Sigma(x is an element of Si) parallel to x - c(S-i)parallel to(2), where c(S-i) denotes the center of gravity of S-i. For k = 2 and for any fixed d and epsilon > 0, we present a deterministic algorithm that finds a 2-clustering with cost no worse than (1 + epsilon)-times the minimum cost in time O(n log n); the constant of proportionality depends polynomially on epsilon. For an arbitrary fixed k, we get an O(n log(k) n) algorithm for a fixed epsilon, again with a polynomial dependence on epsilon.