We address the problem of partitioning a set of $n$ points into
clusters, so as to minimize the sum, over all intracluster pairs of
points, of the cost associated with each pair. We obtain a randomized
approximation algorithm for this problem, for the cost functions
$\ell_2^2,\ell_1$ and $\ell_2$, as well as any cost function
isometrically embeddable in $\ell_2^2$.

The maximization problem (maximize the costs of intercluster edges) is
approximated with high probability to within multiplicative factor
$(1-\ep)$; while the minimization problem either receives a
multiplicative $1+\ep$ approximation, or else the optimal clustering
is correctly identified except for a mislabelling of an $\ep$ fraction
of the point set. Given a fixed approximation parameter $\ep$, the
runtime is linear in $n$ for $\ell_2^2$ problems of dimension
$o(\log n / \log \log n)$; and $n^{O(\log \log n)}$ in the general
case.

The case $\ell_2^2$ is addressed by combining three elements: (a)
Variable-probability sampling of the given points, to reduce the size
of the data set. (b) Near-isometric dimension reduction. (c) A
deterministic exact algorithm which runs in time exponential in the
dimension (rather than the number of points). The remaining cases are
addressed by reduction to $\ell_2^2$.