# N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $$N$$ points so that the sum of all distances between the $$N$$ points is maximized? $$N$$ could be as high as 100.

To calculate the sum of distances for all sets of $$N$$ points would be exponential, which would not scale to 50,000 points.

What is the fastest algorithm that you would know? And also, does this problem have a name? If so, I could do more reading about it.

Thanks very much for your feedback.

• Are these 2D points or what? Is the distance Euclidean? Oct 21 at 16:48
• Are you familiar with Convex Hull? There are algorithms for computing convex hull in time n log n. Then what? Oct 21 at 16:49
• "To calculate the sum of distances for all sets of N points would be exponential". Since the number of points is upper bounded by a constant, this algorithm requires at most constant time, i.e., it is asymptotically optimal. Oct 21 at 17:14
• Surely that's not very helpful Oct 21 at 17:18
• The problem is NP-hard, by reduction from maximum clique (consider 0-1 matrix). Oct 22 at 3:47