Clustering for Edge-Cost Minimization

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 ` 2 2 ; ` 1 and ` 2 , as well as any cost function isometrically embeddable in ` 2 2 . The maximization problem (maximize the costs of intercluster edges) is approximated with high probability to within multiplicative factor (1 \Gamma "); while the minimization problem either receives a multiplicative 1 + " approximation, or else the optimal clustering is correctly identified except for mislabelling of an " fraction of the point set. Given a fixed approximation parameter ", the runtime is linear in n for ` 2 2 problems of dimension o(log n= log log n); and n O(log log n) in the general case. The case ` 2 2 is addressed by combining three elements: (a) Variable-probability sampling of the given points, to reduce the siz..