A sublinear time approximation scheme for clustering in metric spaces

The metric 2-clustering problem is defined as follows: given a metric (or weighted graph) (X, d), partition X into two sets S (1) and S (2) in order to minimize the value of /spl Sigma//sub i//spl Sigma//sub u, v/spl sub/S (i) /d (u, v). In this paper, we show an approximation scheme for this problem.