Most mutually distant k elements (clustering?)

Question

I have a simple machine learning question:

I have n (~110) elements and a matrix of all the pairwise distances. I would like to choose the 10 elements that are most far apart. That is, I want to

Maximize:

  Choose 10 different elements.

  Return min distance over (all pairings within the 10).

My distance metric is symmetric and respects the triangle inequality.

What kind of algorithm can I use? My first instinct is to do the following:

1. Cluster the n elements into 20 clusters.
2. Replace each cluster with just the element of that cluster that is furthest from the mean element of the original n.
3. Use brute force to solve the problem on the remaining 20 candidates. Luckily, 20 choose 10 is only 184,756.

Answer 1

"Return minimum distance over all pairs" in the end line to get something that resembles "most far apart". Just change the "Return sum of (distances)" to "Return min distance" in the optimization problem statement.

 Another direction to look at would be the local search methods such as simulated annealing and hill climbing.

If you wish to learn about k-means clustering then visit this k-means Clustering Tutorial.