<p>Have you seen <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8781">this paper</a> 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.</p>

CC BY-SA 3.0
2013-02-22T07:04:18.410Z
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
CC BY-SA 3.0
2013-02-22T04:25:02.757Z
2013-02-22T04:25:02.757Z
Suresh Venkat
<p>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.</p>

<p>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. </p>

<p>I can give more clarification if required. </p>

<p>[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. </p>

CC BY-SA 3.0
2013-02-21T23:29:50.340Z
More clarification is required.  These problems tend to be sensitive to the precise metric being optimized.
Jeffε
CC BY-SA 3.0
2013-02-21T23:37:07.927Z
Please see edited problem
rajaditya_m
<clustering>
PTAS Algorithm for K-Clustering when Distance Computation is Costly
rajaditya_m
# PTAS Algorithm for K-Clustering when Distance Computation is Costly

(Asked by: username_0 on 2013-02-21)

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.

**Tags:** clustering

> **Comments:**
> **username_1**: More clarification is required.  These problems tend to be sensitive to the precise metric being optimized.  
> **username_0**: Please see edited problem  

---

## 1 answers

### Answer by username_2 on 2013-02-22. Score: 6 | Accepted answer

Have you seen [this paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8781) 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.

> **Comments:**
> **username_0**: Thanks. It does offer me some insights which can be the starting point for me to look for more optimized versions of this problem.  

---

