# Average distance minimization algorithm

1. Nov 1, 2009

### hamster143

This could be a well-known problem, but I looked around and I don't see anything.

Suppose there is a set of points $$p_1, p_2, ... p_N$$. For simplicity, assume Euclidean space of arbitrary dimensionality, but this could be any metric space.

I need to find a new set $$q_1, q_2, ... q_n$$ of n points, where n is less than N, that "approximates" the original set by minimizing the average distance between points in the original set & the new set.

In other words, I need to minimize

$$\sum_1^{i=N} \min_1^{j=n} |p_i-q_j|$$

There's an obvious brute-force solution, but complexity $$n^N$$ makes it completely useless for large N, which could be 1000 or more. I can cook up an iterative algorithm that gives me a local minimum in a reasonable amount of time, but I have no confidence that the local minimum will be anywhere near the global minimum.

Can this problem be solved exactly in polynomial time?

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted