# PTAS Algorithm for K-Clustering when Distance Computation is Costly

Can anyone throw any light on any PTAS algorithm that I can apply for K-Clustering algorithm when the distance computation between the clustering points is costly.

In details, I have a set of N points and I have a customized distance metric between them. I want to compute a set of k clusters such that the cluster centers are far apart while among the clusters the points are very close. This customized distance metric is costly to calculate and hence I would like them to be calculated as less as it can possibly be.

I can give more clarification if required.

[EDIT] So the distance metric I have defined is $D(x,y) = 1 - \rho(x,y)$ where $\rho(x,y)$ is the Pearson Correlation Coefficient between points $x$ and $y$ ( $x$ and $y$ are data sets in themselves). Obviously to compute all such Pearson Correlations Coefficient when the number of data-points is 1000 (each set $x$ has another 1000 or so values within themselves) or so can be very expensive computationally.

-
More clarification is required. These problems tend to be sensitive to the precise metric being optimized. – JɛﬀE Feb 21 '13 at 23:29

Have you seen this paper by Piotr Indyk ? It's old, but it's a good one. It solves a number of problems including k-median while making only sublinear number of calls to the distance oracle. It's not exactly the model you're looking for, but it does try to reduce the number of distance invocations.

-
Thanks. It does offer me some insights which can be the starting point for me to look for more optimized versions of this problem. – rajaditya_m Feb 22 '13 at 7:04