# Finding N most distinct values in set given distance metric

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.

## 1 Answer

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)$.