hamster143
Nov1-09, 05:12 AM
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?
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?