Clustering for Metric and Nonmetric Distance Measures

We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P of size n, our goal is to find a set C of size k such that the sum of errors D(P, C) = Sigma(p is an element of P) min(c is an element of C) {D(p, c)} is minimized. The main result in this article can be stated as follows: There exists a (1 + epsilon)-approximation algorithm for the k-median problem with respect to D, if the I-median problem can be approximated within a factor of (1 + epsilon) by taking a random sample of constant size and solving the I-median problem on the sample exactly. This algorithm requires time n2(O(mklog(mk/epsilon))), where m is a constant that depends only on epsilon and D. Using this characterization, we obtain the first linear time (1 + epsilon)-approximation algorithms for the k-median problem in an arbitrary metric space with bounded doubling dimension, for the Kullback-Leibler divergence (relative entropy), for the Itakura-Saito divergence, for Mahalanobis distances, and for some special cases of Bregman divergences. Moreover, we obtain previously known results for the Euclidean k-median problem and the Euclidean k-means problem in a simplified manner. Our results are based on a new analysis of an algorithm of Kumar et al. [2004].