Average distance minimization algorithm

[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?

 

[Future Bruno]

If so, how?Unfortunately, there is no known polynomial-time solution to this problem. It is a classic example of an NP-hard problem, meaning that it is likely impossible to find an exact solution in polynomial time. There are, however, several approximate algorithms that can be used to find good solutions with reasonable running times. These include the k-means algorithm, the Lloyd–Max algorithm, and the greedy algorithm.

 

[quicknote]

I can offer several potential approaches to this problem. First, it is important to note that this problem falls under the category of optimization, specifically in the field of computational geometry. Similar problems have been studied extensively in the literature, such as the k-means clustering problem and the facility location problem.

One potential solution is to use heuristic or approximation algorithms, which may not guarantee an optimal solution but can provide a reasonable solution in a reasonable amount of time. These algorithms often have better time complexity compared to brute-force approaches and can find a solution that is close to the global minimum. For example, the k-means algorithm is a popular heuristic approach for clustering data points, which can be adapted for this problem by setting k=n.

Another approach is to use metaheuristic algorithms, such as genetic algorithms or simulated annealing, which can explore a larger search space and potentially find a better solution compared to heuristic algorithms. These methods are based on natural processes and can handle large-scale problems with high-dimensional data.

Additionally, there may be specialized algorithms or techniques for specific types of metric spaces, such as Euclidean space, that can provide a more efficient solution. It may also be worth exploring the use of parallel computing to speed up the computation of the brute-force solution, as well as other approaches.

In terms of a polynomial time exact solution, it is unlikely that such a solution exists for this problem. This is due to the fact that the problem falls under the category of NP-hard problems, which means that the time complexity of finding an exact solution grows exponentially with the size of the input. Therefore, it may be more practical to focus on finding efficient approximation or heuristic algorithms for this problem.