1
$\begingroup$

Let's say you are given a set with $V$ vectors and you are given a simple Euclidean distance metric $d(a,b)$ for $a, b \in V$. Then what would be the most efficient algorithm to build a subset $S$ of a desired size $k$ such that the sum of the distances between the elements of the subset is maximized?

In other words, how does one find a subset with the most distinct vectors?

I have tried modeling this as a complete graph where the nodes are vectors and the edges the Euclidean distances between them, but I couldn't find a graph algorithm that solves this problem. It seems like finding an independent set of given size $|S|$ with the maximum number distance between them.

$\endgroup$
2
$\begingroup$

This problem generalizes maximum independent set and its relatives. Indeed, suppose that you could solve your problem. Then you could use the solution for deciding whether a graph contains an independent set of size $k$. Given a graph $G = (V,E)$, form a metric space by setting $d(u,v) = 1$ if $\{u,v\} \in E$ and $d(u,v) = 2$ if $\{u,v\} \notin E$. The graph contains an independent set of size $k$ iff there are $k$ points in the metric space in which the sum of distances is $k(k-1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.