3
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ Are these 2D points or what? Is the distance Euclidean? $\endgroup$
    – Pål GD
    Oct 21 at 16:48
  • $\begingroup$ Are you familiar with Convex Hull? There are algorithms for computing convex hull in time n log n. Then what? $\endgroup$
    – Pål GD
    Oct 21 at 16:49
  • 1
    $\begingroup$ "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. $\endgroup$
    – Steven
    Oct 21 at 17:14
  • 1
    $\begingroup$ Surely that's not very helpful $\endgroup$
    – Pål GD
    Oct 21 at 17:18
  • 2
    $\begingroup$ The problem is NP-hard, by reduction from maximum clique (consider 0-1 matrix). $\endgroup$
    – Dmitry
    Oct 22 at 3:47
1
$\begingroup$

Your problem is known as the maximum diversity problem.

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