# Discrete optimization problem

Suppose you had $N$ many fixed points $X_1, X_2, ..., X_N$ in some Euclidean space $R^d$ and from these coordinates you had to choose $n$ many of them ($n \leq N$ also being fixed) to form a subset $S$ that maximizes the function $f(S) = \sum_{(i,j) \in S \times S} ||X_i-X_j||^2$. How would you choose $S$? Note that $||\cdot||$ is the usual Pythagorean norm.

Informally, you are choosing the n points so that they are as 'distant' from each other as possible. Is there a solution to this problem or at least an algorithmic approach to this problem? Solutions to this problem involving different functions that encode the notion of being 'far apart' would interest me as well.

• Define the matrix $a_{ij}:=\|X_i-X_j\|$ then you are left with the problem of finding a submatrix of size $n\times n$ with maximal sum. However, I dont know if there exist an efficient algorithm for this. So far I only found solution for the contiguous submatrix problem. – user35593 Jun 26 '15 at 6:11
• If $n$ is much smaller than $N$ and you distribute your $N$ points more or less uniformly on the surface of a sphere, then your question is a variant of the Thomson problem (see en.wikipedia.org/wiki/Thomson_problem). This problem is very hard, and it is only a very special case of your problem. So I think it's probably hopeless to find a nice algorithm that works optimally in every situation. So I think the answers of Weis and O'Rourke (or others like those) are probably as good as you can hope for. – Will Brian Jun 26 '15 at 16:40
• @WillBrian: Nice observation re electrons on a sphere. – Joseph O'Rourke Jun 26 '15 at 18:58

Nice question. Here I just mention an interesting idea used in this GIS StackExchange posting by whuber (William Huber): Find $n$ clusters among your $N$ points, and take the center of those clusters as your $n$ points. As he says, "You can see it's not great (but it's not too bad, either)." Below, $N=1000$ (colored points), $n=200$ (gray points): 